插入排序与冒泡排序算法

Question

我正在尝试理解一些排序算法,但我很难看到冒泡排序和插入排序算法的差异.

我知道两者都是O(n ²),但在我看来,冒泡排序只是将每个传递的数组的最大值冒泡到顶部,而插入排序只是将每个传递的最低值放到底部.他们不是在做同样的事情,而是在不同的方向吗？

对于插入排序,比较/潜在交换的数量从零开始并且每次都增加(即0,1,2,3,4,...,n),但是对于冒泡排序,这种行为发生了,但是在结束时排序(即n,n-1,n-2,... 0)因为冒泡排序不再需要与排序后的最后一个元素进行比较.

尽管如此,似乎一致认为插入排序更好.谁能告诉我为什么？

编辑:我主要对算法如何工作的差异感兴趣,而不是他们的效率或渐近复杂性.

Answer 1

插入排序

之后我重复第一我的元素是有序的.

在每次迭代中,下一个元素通过已排序的部分冒泡,直到它到达正确的位置:

sorted  | unsorted
1 3 5 8 | 4 6 7 9 2
1 3 4 5 8 | 6 7 9 2

将4冒泡到已排序的部分

伪代码:

for i in 1 to n
    for j in i downto 2
        if array[j - 1] > array[j]
            swap(array[j - 1], array[j])
        else
            break

冒泡排序

之后我迭代最后我的元素是最大的,并下令.

在每次迭代中,筛选未排序的部分以找到最大值.

unsorted  | biggest
3 1 5 4 2 | 6 7 8 9
1 3 4 2 | 5 6 7 8 9

5是从未分类的部分冒出来的

伪代码:

for i in 1 to n
    for j in 1 to n - i
         if array[j] > array[j + 1]
             swap(array[j], array[j + 1])

请注意,如果在外部循环的一次迭代期间没有进行交换,则典型的实现会提前终止(因为这意味着数组已排序).

区别

在插入中,排序元素被冒泡到排序部分,而在冒泡排序中,最大值被排出未排序部分.

Answer 2

在第i次迭代的冒泡排序中,你总共有ni-1内迭代(n ^ 2)/ 2,但是在插入排序中,你在第i步上有最大的i次迭代,但平均来说是i/2,因为你可以停止内部循环之前,在找到当前元素的正确位置之后.所以你有(总和0到n)/ 2总共(n ^ 2)/ 4;

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

Answer 3

另一个区别,我没有在这里看到:

冒泡排序每个交换有3个值分配:你必须首先构建一个临时变量以保存你想要前进的值(1号),而不是必须将另一个交换变量写入刚刚保存值的位置(No.2)然后你必须在现场其他地点(3号)写你的临时变量.你必须为每个点做到这一点 - 你想要前进 - 将你的变量排序到正确的位置.

使用插入排序,您可以将变量放入临时变量中,然后将所有变量放在该点之前1个点向后,只要您到达变量的正确位置即可.这使得每个点有1个值的分配.最后,你将临时变量写入现场.

这也远不是价值分配.

这不是最强的速度效益,但我认为可以提及.

我希望,我表达自己可以理解,如果不是,对不起,我不是英国人

Answer 4

插入排序的主要优点是它是在线算法.您不必在开始时拥有所有值.在处理来自网络或某些传感器的数据时,这可能很有用.

我有一种感觉,这比其他传统n log(n)算法更快.因为复杂性将是n*(n log(n))例如从stream(O(n))读取/存储每个值,然后对所得到的值(O(n log(n)))进行排序O(n^2 log(n))

相反,使用Insert Sort需要O(n)从流中读取值O(n)并将值放到正确的位置,因此它是O(n^2)唯一的.其他优点是,您不需要缓冲区来存储值,您可以在最终目标中对它们进行排序.

Answer 5

冒泡排序不在线(它不能在不知道将有多少项目的情况下对输入流进行排序),因为它并不真正跟踪已排序元素的全局最大值.插入项目时,您需要从一开始就开始冒泡

Answer 6

仅当某人从大量数字中查找前k个元素时，冒泡排序才比插入排序好，即在k次迭代后进行冒泡排序时，您将获得前k个元素。但是，在插入排序中进行了k次迭代之后，它仅确保对这k个元素进行了排序。