请问插入排序和冒泡排序的算法差异

Question

请问这两种算法的差异在哪里呢

Answer 1

liuyubobobo 2018-09-17 15:36:44

这个课程并没有介绍冒泡排序，因为我个人并不认为冒泡排序的思想是一个很有意义的算法思想。但在这个课程的后续，你将看到插入排序有着重要的作用。

我相信通过这个课程的学习，你已经理解了插入排序了。简单说一下和冒泡排序的不同：

1）

冒泡排序在第k轮循环以后，保证的是最后k个数字有序；

而插入排序在第k轮循环以后，保证的是前k个数字有序；

2）

冒泡排序在第k轮循环以后，最后k个数字就是整个数组排序后的结果，即最后k个数字就是整个数组top k大的数字；

而插入排序在第k轮循环以后，前k个数字还是原来数组中的前k个数字。此时，最小值不一定在前k个数字中，可能在后续还没有处理。

比较一下，对于冒泡排序，第一轮循环以后，最大的数字就已经放在最后的位置了；第二轮循环以后，第二大的数字就已经放在倒数第二的位置了，以此类推...

整体，如果对这个问题感兴趣，建议你使用同一个测试用例，使用插入排序，也是用冒泡排序，将两种排序每一轮循环后，数组变成什么样子打印出来，首先仔细想明白两种算法的运行原理，为什么会得到这样的结果，再仔细比较两种算法的不同。

使用小数据样例，跟进算法内部，仔细去看，去研究，算法的每一部运行后，数据产生了怎样的变化，为什么会有这样的变化，是非常重要的学习算法，深入理解算法的方式哦。进步就发生在这个过程里：）

加油！：）

• 提问者 tataxqy #1

  非常感谢！