bubble-sort - 插入和冒泡算法理论

Question

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

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

标签： bubble-sortinsertion-sort

Answer 1

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

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