使用插入排序来优化可以这样写吗？
public static <E extends Comparable<E>> void sortBU(E[] arr) {
E[] temp = Arrays.copyOf(arr, arr.length);
int n = arr.length;
for (int size = 1; size < n; size += size) {
//长度在15之用插入
if (size <= 15) {
for (int i = 0; i + size < n; i += size + size) {
if (arr[i + size - 1].compareTo(arr[i + size]) > 0) {
InsertionSort.sort4(arr, i, Math.min(i + size + size - 1, n - 1));
}
}
}
//长度大于15用归并
else{
for (int i = 0; i + size < n; i += size + size) {
if (arr[i + size - 1].compareTo(arr[i + size]) > 0) {
merge2(arr, i, i + size - 1, Math.min(i + size + size - 1, n - 1), temp);
}
}
}
}
}10
收起
正在回答 回答被采纳积分+1
1回答
liuyubobobo
2022-07-09 07:30:58
抱歉，这个提问慕课网的系统通知没有提醒到我，我今天查看后台数据才看到。
==========
你的代码可以正确的排序，但是其中做了一部分无用功。
因为你的代码会在 sz = 1, 2, 4, 8 的时候，分别对数组中长度为 2, 4, 8, 16 的子数组做插入排序。这是没有必要的。对长度为 2 的子数组做插入排序，并不能特别帮助对长度为 4 的子数组做插入排序。 我们的优化，只需要对所有长度为 16 的子数组做插入排序，就够了。之后就可以开始归并排序的过程。
其中 34-35 行只运行了一轮，儿你的代码，在插入排序部分，运行了多轮。
继续加油！：）
相似问题
登录后可查看更多问答，登录/注册
恭喜解决一个难题，获得1积分~
来为老师/同学的回答评分吧
0 星