请问插入排序和冒泡排序的算法差异
来源：2-4 测试算法的性能
tataxqy
2018-09-17
请问这两种算法的差异在哪里呢
写回答
1回答
-
这个课程并没有介绍冒泡排序，因为我个人并不认为冒泡排序的思想是一个很有意义的算法思想。但在这个课程的后续，你将看到插入排序有着重要的作用。
我相信通过这个课程的学习，你已经理解了插入排序了。简单说一下和冒泡排序的不同：
1）
冒泡排序在第k轮循环以后，保证的是最后k个数字有序；
而插入排序在第k轮循环以后，保证的是前k个数字有序；
2）
冒泡排序在第k轮循环以后，最后k个数字就是整个数组排序后的结果，即最后k个数字就是整个数组top k大的数字；
而插入排序在第k轮循环以后，前k个数字还是原来数组中的前k个数字。此时，最小值不一定在前k个数字中，可能在后续还没有处理。
比较一下，对于冒泡排序，第一轮循环以后，最大的数字就已经放在最后的位置了；第二轮循环以后，第二大的数字就已经放在倒数第二的位置了，以此类推...
整体，如果对这个问题感兴趣，建议你使用同一个测试用例，使用插入排序，也是用冒泡排序，将两种排序每一轮循环后，数组变成什么样子打印出来，首先仔细想明白两种算法的运行原理，为什么会得到这样的结果，再仔细比较两种算法的不同。
使用小数据样例，跟进算法内部，仔细去看，去研究，算法的每一部运行后，数据产生了怎样的变化，为什么会有这样的变化，是非常重要的学习算法，深入理解算法的方式哦。进步就发生在这个过程里：）
加油！：）
212018-09-27
相似问题