关于插入排序优化的问题
来源：2-3 插入排序法的一个小优化
蛋包饭吃球球
2021-07-06 15:09:00
问题描述：
bobo老师您好！我自己试着实现了一下插入排序的优化，没有找出什么问题。问题在有无break语句。我感觉应该有（或者说无所谓），因为发现应该插入的地方时，第i个元素就已经找到了适合它的位置，本次循环结束了。但为什么有break测试时没报错，但时间明显是错的。没有break反而测试是正确的呢？
相关截图：
第一张图是有break语句的测试
第二张是删掉break语句后的测试
相关代码：
麻烦bobo老师了~
写回答
1回答
-
你的程序完全是不正确的。因为你的 temp 放在了第二层循环里。
这将使得，如果在第一次运行的时候，arr[i] < arr[i - 1] 的话，就会执行 arr[i] = arr[i - 1]，那么在下一轮，temp 就变了。也就是内层循环没有根据一个固定的 arr[i] 的值，寻找其该插入的位置。
更关键的是，这将改变整个数组的值。
你可以使用一个小数据测试一下，比如下面的测试，用 [5, 4, 3, 2, 1] 测试，最终的结果，整个数组变成了 [5, 5, 5, 5, 5]
public static void main(String[] args){ Integer[] arr = {5, 4, 3, 2, 1}; sort2(arr); for(int e: arr) System.out.println(e); }至于为什么加了 break 会快，是因为加上 break，这是整个算法其实是 O(n) 的。不过由于这个算法本身是错的，我们也没必要进一步仔细分析他了。
我们的 test 函数为什么没有报错，这是我们的 test 的局限性。我们只检查了有序性，但是并没有检查数组的元素和原数组是一致的。毕竟 [5, 5, 5, 5, 5] 也是一个有序数组。
所以，我们的测试代码是不严谨的。不过鉴于这个课程本身也不是专门的测试课程，我们也就不再测试方面着墨太多啦：）
继续加油！：）
0hp>感谢bobo老师，我终于改对了我的代码！！！之前确实是逻辑错误的， 谢谢你的耐心回答~
h021-07-06
相似问题