Java中含90%重复值的数组排序：最优算法选择

Great question! When your array has around 90% duplicate elements, standard sorting algorithms that rely heavily on element comparisons can end up doing a ton of unnecessary work. Let’s break down the best options for this specific scenario in Java:

1. 三路快速排序（Three-Way QuickSort） #

This is hands-down one of the best choices for arrays with massive duplication. Unlike regular quicksort (or even Java’s default dual-pivot quicksort for primitives), three-way quicksort splits the array into three distinct partitions during each pass:

• Elements smaller than the pivot
• Elements equal to the pivot
• Elements larger than the pivot

The magic here is that the entire "equal to pivot" section is already sorted—we don’t need to touch it in subsequent recursive calls. With 90% of your elements being the same, this means most of your array gets skipped after the first few passes, leading to way faster performance than standard sorts.

Here’s a simplified Java implementation snippet to illustrate the core logic:

public static void threeWayQuickSort(int[] arr, int low, int high) {
    if (high <= low) return;
    int lt = low, gt = high;
    int pivot = arr[low];
    int i = low;
    while (i <= gt) {
        if (arr[i] < pivot) swap(arr, lt++, i++);
        else if (arr[i] > pivot) swap(arr, i, gt--);
        else i++;
    }
    threeWayQuickSort(arr, low, lt - 1);
    threeWayQuickSort(arr, gt + 1, high);
}

private static void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

2. 计数排序（Counting Sort） #

If your array elements fall within a small, known range (e.g., integers between 0 and 100, or enum values), counting sort is unbeatable—it runs in linear time O(n + k) where k is the range of values. Since it doesn’t use comparisons at all, it avoids all the overhead of comparison-based sorts when duplicates are abundant.

Here’s how you’d implement it in Java for an integer array:

public static void countingSort(int[] arr) {
    if (arr.length == 0) return;
    
    // Find min and max to determine range
    int min = arr[0], max = arr[0];
    for (int num : arr) {
        if (num < min) min = num;
        if (num > max) max = num;
    }
    
    int range = max - min + 1;
    int[] count = new int[range];
    
    // Count occurrences of each element
    for (int num : arr) {
        count[num - min]++;
    }
    
    // Reconstruct the sorted array
    int index = 0;
    for (int i = 0; i < range; i++) {
        while (count[i] > 0) {
            arr[index++] = i + min;
            count[i]--;
        }
    }
}

What about Java’s built-in Arrays.sort()? #

Java’s default Arrays.sort() uses dual-pivot quicksort for primitive types and TimSort (a hybrid of merge sort and insertion sort) for objects. While these are great general-purpose sorts, they don’t optimize specifically for high duplication. Dual-pivot quicksort will still do a lot of redundant comparisons on your 90% duplicate elements, and TimSort’s performance will be good but not as optimal as the two options above for this edge case.

Final Recommendation #

• Use counting sort if your elements have a small, bounded range. It’s the fastest possible option here.
• Use three-way quicksort if your element range is large (or non-integer/non-enum). It cuts down on unnecessary work by skipping duplicate elements entirely during recursion.

内容的提问来源于stack exchange，提问作者A.khaled