插入排序与冒泡排序算法

本文介绍了插入排序与冒泡排序算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我试图理解一些排序算法，但是我正努力查看气泡排序和插入排序算法的区别。

I'm trying to understand a few sorting algorithms, but I'm struggling to see the difference in the bubble sort and insertion sort algorithm.

我都知道是O（n 2 ），但是在我看来，冒泡排序只会使每次通过时数组的最大值冒泡到顶部，而插入排序只会使每次通过时将最小值冒到底部。 。他们不是在做完全一样的事情，只是朝着不同的方向做吗？

I know both are O(n2), but it seems to me that bubble sort just bubbles the maximum value of the array to the top for each pass, while insertion sort just sinks the lowest value to the bottom each pass. Aren't they doing the exact same thing but in different directions?

对于插入排序，比较/潜在交换的次数从零开始，每次增加（即0） ，1、2、3、4，...，n），但对于冒泡排序，会发生相同的行为，但在排序结束时（即n，n-1，n-2，... 0），因为冒泡排序时，排序不再需要与最后一个元素进行比较。

For insertion sort, the number of comparisons/potential swaps starts at zero and increases each time (ie 0, 1, 2, 3, 4, ..., n) but for bubble sort this same behaviour happens, but at the end of the sorting (ie n, n-1, n-2, ... 0) because bubble sort no longer needs to compare with the last elements as they are sorted.

尽管如此，似乎人们普遍认为插入排序通常更好。谁能告诉我为什么？

For all this though, it seems a consensus that insertion sort is better in general. Can anyone tell me why?

编辑：我主要对算法工作方式的差异感兴趣，而不是效率和渐进复杂性。 / em>

I'm primarily interested in the differences in how the algorithms work, not so much their efficiency or asymptotic complexity.

推荐答案

在第i次迭代中进行冒泡排序时，您共有ni-1个内部迭代（n ^ 2）/ 2，但是在插入排序中，您在第i步的迭代次数最多，但平均为i / 2，因为您可以在找到当前元素的正确位置后更早地停止内循环。所以你有（从0到n的总和）/ 2，共（n ^ 2）/ 4；

In bubble sort in ith iteration you have n-i-1 inner iterations (n^2)/2 total, but in insertion sort you have maximum i iterations on i'th step, but i/2 on average, as you can stop inner loop earlier, after you found correct position for the current element. So you have (sum from 0 to n) / 2 which is (n^2) / 4 total;

这就是为什么插入排序比气泡排序更快的原因。

That's why insertion sort is faster than bubble sort.