java Arrays.sort(Object[] a) - 它是如何实现的？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2218041/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Arrays.sort(Object[] a) - how is it implemented?
提问by helpermethod
Are there any resources on how the mergeSort used by Arrays.sort(Object[] a) is implemented? While it is documented quite good, I have a hard time understanding it (especially why the src and dest are are switched when mergeSort() get's recursively called).
是否有任何关于如何实现 Arrays.sort(Object[] a) 使用的 mergeSort 的资源？虽然它的文档非常好，但我很难理解它（尤其是为什么在递归调用 mergeSort() get 时切换 src 和 dest）。
回答by Bozho
Here is the sourceof java.util.Arrays.
这里是源的java.util.Arrays。
Actually, you have that source code in the JDK - just open java.util.Arraysin your IDE and the source code + the comments will appear. If you don't have an IDE, look at JDK_HOME\src.zip
实际上，您在 JDK 中有该源代码 - 只需java.util.Arrays在您的 IDE 中打开，源代码 + 注释就会出现。如果您没有IDE，请查看JDK_HOME\src.zip
Then, put it in your IDE and trace how it works.
然后，将它放入您的 IDE 并跟踪它的工作原理。
- put breakpoints (and run a program in debug mode)
- use
System.out.println(..) - change parts of it to see how they are reflected.
- read the wikipedia article about merge sort
- pay attention to this comment:
// Recursively sort halves of dest into src
- 放置断点（并在调试模式下运行程序）
- 利用
System.out.println(..) - 改变它的一部分，看看它们是如何反映的。
- 阅读维基百科关于归并排序的文章
- 注意这个评论：
// Recursively sort halves of dest into src
回答by lostinmoney
I ever had the same confusion with you. According to my understanding, the reason for this switching is very simple - make followed merging step easier. No magic.
我和你也有过同样的困惑。根据我的理解，这种切换的原因很简单——让后续的合并步骤更容易。没有魔法。
private static void mergeSortWithoutSwitch(Object[] src, Object[] dest, int low, int high, int off) {
int length = high - low;
// Insertion sort on smallest arrays
if (length < INSERTIONSORT_THRESHOLD) {
for (int i = low; i < high; i++)
for (int j = i; j > low && ((Comparable) dest[j - 1]).compareTo(dest[j]) > 0; j--)
swap(dest, j, j - 1);
return;
}
// Recursively sort halves of dest into src
int destLow = low;
int destHigh = high;
low += off;
high += off;
int mid = (low + high) >>> 1;
mergeSortWithoutSwitch(src, dest, low, mid, off);
mergeSortWithoutSwitch(src, dest, mid, high, off);
// If list is already sorted, just copy from src to dest. This is an
// optimization that results in faster sorts for nearly ordered lists.
if (((Comparable) dest[mid - 1]).compareTo(dest[mid]) <= 0) {
return;
}
// Merge sorted halves (now in src) into dest
for (int i = destLow, p = low, q = mid; i < destHigh; i++) {
if (q >= high || p < mid && ((Comparable) dest[p]).compareTo(dest[q]) <= 0)
src[i] = dest[p++];
else
src[i] = dest[q++];
}
// copy back
for (int i = destLow; i < destHigh; i++) {
dest[i] = src[i];
}
}
Above is the implementation without switching, from the code, you can see we need one more step in merging - copy back. I think the parameter naming in mergeSort is a little confused, since the src is auxiliary array which is only used in merging step, it will be better to name it with aux (We can even remove it from method signature, and create a local variable when merging). And dest is the result array.
以上是没有切换的实现，从代码中可以看出我们还需要多一步合并——copy back。我觉得mergeSort中的参数命名有点混乱，因为src是辅助数组，只在合并步骤中使用，最好用aux命名（我们甚至可以从方法签名中删除它，并创建一个局部变量合并时）。dest 是结果数组。
