为什么 Java 排序优于原语计数排序

Question

我正在比较计数排序的运行ning 时间与 Java 原生 Arrays.sort。从我读过的内容来看，计数排序提供了 n+k 运行ning 时间的最佳、平均和最坏情况。 Javas Arrays sort of primitives, using a dual-pivot Quicksort, is a comparison based algorithm 因此必须在平均情况下提供 O(n log n)，在最坏情况下提供 On2。

通过测量对大小为 500 到 100k 的一系列数组进行排序所花费的时间（纳秒）来比较两者时，我注意到当大小达到时运行计数排序的时间急剧增加~70k。

我的理解是，只要输入数据的范围不明显大于要排序的元素数，计数排序就是有效的这些数组是从 0 到 99 之间的随机数构建的，因此 k 总是比 n 小得多。

计数排序会随着 n 的增加而如此突然地退化是否有任何特殊原因？

我的计数排序实现：

public static int[] countSort(int[] arr, int k) {
        /*
         * This will only work on positive integers 0 to K.
         * For negative  worst case testing we use the negative count sort below.
         * 
         * Step 1: Use an array to store the frequency of each element. For array
         * elements 1 to K initialize an array with size K. Step 2: Add elements of
         * count array so each element stores summation of its previous elements. Step
         * 3: The modified count array stores the position of elements in actual sorted
         * array. Step 5: Iterate over array and position elements in correct position
         * based on modified count array and reduce count by 1.
         */

        int[] result = new int[arr.length];
        int[] count = new int[k + 1];
        for (int x = 0; x < arr.length; x++) {
            count[arr[x]]++;
        }

        /*
         * Store count of each element in the count array Count[y] holds the number of
         * values of y in the array 'arr'
         */

        for (int y = 1; y <= k; y++) {
            count[y] += count[y - 1];
        }

        /*
         * Change count[i] so that count[i] now contains actual Position of this element
         * in result array
         */

        for (int i = arr.length - 1; i >= 0; i--) {
            result[count[arr[i]] - 1] = arr[i];
            count[arr[i]]--;
        }

        System.out.println("COUNTSORT SORTED ARRAY = " + Arrays.toString(result));
        return result;

    }

分辨率： 运行根据@Alex 的建议，计数排序产生了更优越的运行时间。

Answer 1

只是一个猜测，但您的排序算法使用的内存比 Java 的多得多。 70k 的整数是 280KB。您需要 space 的两倍，超过 512KB。根据所使用的处理器，这可能会导致运行在（L1？）缓存中的排序和大量缓存未命中之间的差异。因为你真的不需要副本，所以就地排序。如果你现在碰壁了，你就有答案了。

编辑：280KB。

Edit2: 昨天来晚了，就地版来了。请注意，它修改了输入数组。

public static int[] countSortRefactored(int[] arr, int k) {
    int[] count = new int[k + 1];
    for (int x = 0; x < arr.length; x++) {
        count[arr[x]]++;
    }

    int idx=0;
    for (int x=0; x<=k; x++) {
        Arrays.fill(arr, idx, idx+=count[x], x);
    }

    System.out.println("COUNTSORT SORTED ARRAY = " + Arrays.toString(arr));
    return arr;
}

为什么 Java 排序优于原语计数排序

Why does Java sort outperform Counting sort for primitives

java

performance

sorting

counting-sort