寻找适用于连续数字的高效Java排序算法

如果你要排序的是连续整数，那直接用计数排序就好——它能做到O(n)的线性时间复杂度，比快速排序的O(nlogn)高效得多，完全适配你数千级别的数据量。下面详细说实现和注意点：

为什么计数排序适合？ #

连续数字的核心特点是取值范围明确且跨度小（或跨度与数据量正相关），计数排序不需要通过元素比较来排序，而是直接基于数值的位置统计和还原，彻底避开了比较排序的O(nlogn)下界。

计数排序的Java实现 #

import java.util.Arrays;

public class CountingSort {
    public static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) return;

        // 找出数组的最小、最大值，确定连续范围
        int min = arr[0], max = arr[0];
        for (int num : arr) {
            if (num < min) min = num;
            if (num > max) max = num;
        }

        // 计数数组长度等于连续数字的个数
        int countSize = max - min + 1;
        int[] count = new int[countSize];

        // 统计每个数字出现的次数
        for (int num : arr) {
            count[num - min]++;
        }

        // 把统计结果还原成排序后的数组
        int idx = 0;
        for (int i = 0; i < countSize; i++) {
            while (count[i]-- > 0) {
                arr[idx++] = i + min;
            }
        }
    }

    public static void main(String[] args) {
        int[] testArr = {7, 3, 5, 3, 9, 7, 5};
        sort(testArr);
        System.out.println(Arrays.toString(testArr)); // 输出 [3, 3, 5, 5, 7, 7, 9]
    }
}

备选方案：桶排序 #

如果你的连续数字是带小数的（比如1.0, 1.1, 1.2...），或者想更灵活处理区间，桶排序是计数排序的扩展。对于整数连续数字，桶排序可以简化为每个桶存一个数值，效果和计数排序一致：

import java.util.ArrayList;
import java.util.List;

public class BucketSort {
    public static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) return;

        int min = arr[0], max = arr[0];
        for (int num : arr) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }

        // 每个桶对应一个连续整数
        List<Integer>[] buckets = new List[max - min + 1];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 把元素放进对应桶
        for (int num : arr) {
            buckets[num - min].add(num);
        }

        // 合并桶得到排序结果
        int idx = 0;
        for (List<Integer> bucket : buckets) {
            for (int num : bucket) {
                arr[idx++] = num;
            }
        }
    }

    public static void main(String[] args) {
        int[] testArr = {104, 101, 103, 102, 104, 101};
        sort(testArr);
        for (int num : testArr) {
            System.out.print(num + " ");
        }
    }
}

和你用过的排序算法对比 #

• 简单选择排序O(n²)的效率完全没法比，直接淘汰。
• 快速排序虽然平均O(nlogn)，但本质是比较排序，在连续数字场景下，计数排序的线性时间是理论最优的，实际运行速度也会更快——毕竟少了大量的比较、交换操作。

注意事项 #

• 计数排序的空间开销是O(k)，k是连续数字的范围跨度。如果你的"连续数字"是指数值连续但范围极大（比如数组只有1000个元素，但数字是从1到1000000的连续值），那计数排序的空间成本太高，这时候还是用快速排序更划算。但如果是严格连续的数千个数字（比如数组长度n，数字范围是m到m+n-1），空间开销只有O(n)，完全没问题。
• 如果是连续浮点数，可以先把数值乘以一个倍数转成整数（比如1.1*10=11），用计数排序后再转回去，或者用桶排序划分小区间处理。

内容的提问来源于stack exchange，提问作者Vraj