这性能相差也太大了吧。。
来源：2-3 插入排序法的一个小优化
认真努力小封同学
2022-02-25 16:42:27
// sort1
public static <E extends Comparable<E>> void sort(E[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = i; j > 0 && arr[j].compareTo(arr[j - 1]) < 0; j--) {
swap(arr, j, j - 1);
}
}
}
// sort2
public static <E extends Comparable<E>> void sort2(E[] arr) {
for (int i = 0; i < arr.length; i++) {
int j;
for (j = i; j > 0 && arr[i].compareTo(arr[j - 1]) < 0; j--) {
arr[j] = arr[j - 1];
}
arr[j] = arr[i];
}
}写回答
1回答
-
liuyubobobo
2022-02-26
你的 sort2 是错误的。在做课程中介绍的优化的时候，课程官方代码中的 E t = arr[i] 不能省：https://git.imooc.com/class-105/Play-Algorithms-and-Data-Structures/src/master/04-Insertion-Sort/03-Insertion-Sort-Optimized/src/InsertionSort.java
循环中每次是 arr[j - 1] 和 t 作比较，而不是 arr[j - 1] 和 arr[i] 作比较。因为在你的复制过程中，会修改 arr[i] 的值。
用一个小测试用例，实际运行你的 sort2，然后将排序结果打印出来，看看是不是整个数组被修改了？
继续加油！：）
0h022-02-26
相似问题