归并排序自底向上的Java版本代码疑似有误

来源：3-4 自底向上的归并排序算法

Richard0328

2017-11-25

老师您好，我看了您的归并排序自底向上的Java版本代码，运行以后，打印数组出来，发现打印出来的数组不是有序的，我怀疑是您的代码有问题，您有时间可以看一下吗？是经过优化的那里

//        // Merge Sort Bottom Up 优化
//        // 对于小数组, 使用插入排序优化
        for (int i = 0; i < n; i += 16)
            InsertionSort.sort(arr, i, Math.min(i + 15, n - 1));

        for (int sz = 16; sz < n; sz += sz)
            for (int i = 0; i < n - sz; i += sz + sz)
                // 对于arr[mid] <= arr[mid+1]的情况,不进行merge
                if (arr[i + sz - 1].compareTo(arr[i + sz]) > 0)
                    merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1));

写回答

1回答

liuyubobobo

2017-11-25

请确定你实验的代码和我github上的代码一致：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/Course%20Code%20(Java)/04-Merge-Sort-Bottom-Up/src/bobo/algo/MergeSortBU.java

我刚才跑了10万组测试用例，没有问题。如果确认和我的代码一致的话，能否给我一组在我的代码下运行会出错误的测试用例？谢谢！

liuyubobobo

qq_红_14

赞！对，这个问题之前有同学提出过。github代码很早以前就对这个问题进行了更正。现在的代码可以参见https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/Course%20Code%20(Java)/04-Merge-Sort-Bottom-Up/src/bobo/algo/InsertionSort.java 注意这个类里有两个sort，第一个sort是arr[0...n)的插入排序，第二个sort是arr[l...r]的排序，只有第二个sort涉及这个问题。这个文件的修正时间在2017年8月12日，修正历史参见这个commitment:https://github.com/liuyubobobo/Play-with-Algorithms/commit/ed96f956d6deadd6a5790ddb84421331d55df8e0#diff-067b188be5ee48941bcc28809ec70b9a ：）我有时间提醒一下慕课网的同学更新一下在慕课网上的代码：）

2018-02-26

共4条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

查看课程

相似问题

自底向上的归并排序的java代码问题

回答 1

为何有递归的自顶向下的排序方法要快？

回答 2

自底向上归并排序在2^n+1大小的数据集上是否性能会比较差？

回答 1

针对链表自底向上的递归排序

回答 1

为什么插入排序会远远由于归并排序？

回答 1

打开慕课网App查看更多内容