插入和冒泡算法理论

Question

插入排序算法和冒泡排序算法有什么区别？

我到处搜索，但没有找到确切的答案

Answer 1

插入排序将数组分为两部分，一个已排序的部分和一个未排序的部分。该算法获取未排序部分的第一个元素并将其插入已排序部分的正确位置。因为它试图在每个元素出现时放置它们，所以排序的部分可能经常被重写，这是相当昂贵的。

相比之下，冒泡排序遍历数组并一次比较两个值。较大（或较小 [取决于您的实现]）值被推到数组的末尾（冒泡），然后它查看接下来的两个值（刚刚冒泡的一个和下一个）。当算法遍历数组时，最大（或最小）值是数组中的最后一个值。它重复这个过程（在数组的末尾保留排序的值不变）直到数组被排序。如果不是每次都交换值，而只是标记最大值，则可以每次迭代交换一次来实现。