Arrays.sort(Object[] a) - 它是如何实现的？

Question

是否有关于如何实现 Arrays.sort(Object[] a) 使用的 mergeSort 的资源？虽然它的文档记录得很好，但我很难理解它（特别是为什么当递归调用 mergeSort() get 时 src 和 dest 会被切换）。

Answer 1

这是来源 的 java.util.Arrays.

实际上，您在 JDK 中有该源代码 - 只需打开 java.util.Arrays 在你的 IDE 和源代码中+注释将会出现。如果你没有 IDE，请查看 JDK_HOME\src.zip

然后，将其放入 IDE 中并跟踪其工作原理。

• 设置断点（并在调试模式下运行程序）
• 使用 System.out.println(..)
• 更改其中的某些部分以查看它们是如何反映的。
• 阅读 维基百科关于合并排序的文章
• 注意这个评论： // Recursively sort halves of dest into src

Answer 2

我曾经有过与你同样的困惑。根据我的理解，这个切换的原因很简单 - 让其次合成步骤更容易。无幻

    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];
    }

}

以上是无需切换的实现，从代码，你可以看到，我们需要在合并一个步骤 - 复制回来。我觉得参数命名的归并是有点困惑，因为src为这是只有在合并步骤中使用辅助阵列，这将是更好地辅助进行命名（我们甚至可以从方法签名删除它，并创建一个局部变量合并时）。和dest是结果阵列。