每日算法 — 使用java实现计数排序：线性时间非比较排序与稳定性保证

算法概述

计数排序（Counting Sort）是一种非基于比较的排序算法，由Harold Seward于1954年提出。它的核心思想是：对于待排序数组中的每个元素x，确定小于x的元素个数，从而将x直接放到输出数组中的正确位置。

核心特点

• 时间复杂度O(n+k)：n为元素个数，k为元素取值范围
• 空间复杂度O(n+k)：需要额外的计数数组和输出数组
• 稳定性：稳定的排序算法，相等元素的相对顺序不变
• 适用范围：仅适用于整数或有限范围内的数据

算法步骤

1. 统计频次：遍历数组，统计每个值出现的次数，存入计数数组count
2. 累积计数：将count数组转换为累积计数，count[i]表示小于等于i的元素个数
3. 放置元素：从后向前遍历原数组，根据累积计数将元素放到输出数组的正确位置

Java完整实现

import java.util.Arrays;

/**
 * 计数排序完整Java实现
 * 包含基础版本、稳定版本、原地版本及负数支持版本
 */
public class CountingSort {

    /**
     * 标准计数排序（支持非负整数）
     * 时间复杂度：O(n + k)，空间复杂度：O(n + k)
     * @param arr 待排序数组（元素为非负整数）
     * @return 排序后的新数组
     */
    public static int[] sort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return arr == null ? null : arr.clone();
        }

        // 找到最大值以确定计数数组大小
        int max = arr[0];
        for (int num : arr) {
            if (num > max) max = num;
            if (num < 0) throw new IllegalArgumentException("标准计数排序不支持负数");
        }

        return sortWithRange(arr, 0, max);
    }

    /**
     * 已知取值范围的计数排序
     */
    public static int[] sortWithRange(int[] arr, int min, int max) {
        int n = arr.length;
        int range = max - min + 1;

        // 计数数组：记录每个值出现的次数
        int[] count = new int[range];
        for (int num : arr) {
            count[num - min]++;
        }

        // 累积计数：count[i]表示小于等于i的元素个数
        for (int i = 1; i < range; i++) {
            count[i] += count[i - 1];
        }

        // 从后向前遍历，保证稳定性
        int[] output = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            int val = arr[i];
            int pos = count[val - min] - 1;
            output[pos] = val;
            count[val - min]--;
        }

        return output;
    }

    /**
     * 支持负数的计数排序
     */
    public static int[] sortWithNegative(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return arr == null ? null : arr.clone();
        }

        int min = arr[0], max = arr[0];
        for (int num : arr) {
            if (num < min) min = num;
            if (num > max) max = num;
        }

        return sortWithRange(arr, min, max);
    }

    /**
     * 原地计数排序（不返回新数组，修改原数组）
     * 适用于已知范围的小整数
     */
    public static void sortInPlace(int[] arr, int min, int max) {
        int range = max - min + 1;
        int[] count = new int[range];

        // 统计频次
        for (int num : arr) {
            count[num - min]++;
        }

        // 按顺序写回原数组
        int index = 0;
        for (int i = 0; i < range; i++) {
            while (count[i]-- > 0) {
                arr[index++] = i + min;
            }
        }
    }

    /**
     * 对象数组计数排序（基于某个整数字段）
     * 演示稳定排序特性
     */
    static class Student {
        int score;
        String name;

        Student(int score, String name) {
            this.score = score;
            this.name = name;
        }

        @Override
        public String toString() {
            return name + "(" + score + ")";
        }
    }

    public static Student[] sortStudentsByScore(Student[] students, int minScore, int maxScore) {
        int n = students.length;
        int range = maxScore - minScore + 1;

        int[] count = new int[range];
        for (Student s : students) {
            count[s.score - minScore]++;
        }

        for (int i = 1; i < range; i++) {
            count[i] += count[i - 1];
        }

        Student[] output = new Student[n];
        // 从后向前遍历保证稳定性：相同分数的学生保持原有顺序
        for (int i = n - 1; i >= 0; i--) {
            int score = students[i].score;
            int pos = count[score - minScore] - 1;
            output[pos] = students[i];
            count[score - minScore]--;
        }

        return output;
    }

    /**
     * 验证排序正确性
     */
    public static boolean isSorted(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1]) return false;
        }
        return true;
    }

    /**
     * 性能对比：计数排序 vs 快速排序
     */
    public static void performanceComparison() {
        int[] sizes = {1000, 10000, 100000};
        int range = 1000; // 取值范围0-999

        System.out.println("性能对比（范围0-" + (range - 1) + "）：");
        System.out.println("规模      计数排序(ms)    Arrays.sort(ms)");

        for (int size : sizes) {
            int[] arr1 = new int[size];
            int[] arr2 = new int[size];
            for (int i = 0; i < size; i++) {
                arr1[i] = arr2[i] = (int)(Math.random() * range);
            }

            long start1 = System.currentTimeMillis();
            sortWithRange(arr1, 0, range - 1);
            long time1 = System.currentTimeMillis() - start1;

            long start2 = System.currentTimeMillis();
            Arrays.sort(arr2);
            long time2 = System.currentTimeMillis() - start2;

            System.out.println(size + "     " + time1 + "       " + time2);
        }
    }

    public static void main(String[] args) {
        // 测试基本排序
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("原始数组：" + Arrays.toString(arr));
        int[] sorted = sort(arr);
        System.out.println("排序结果：" + Arrays.toString(sorted));
        System.out.println("是否正确排序：" + isSorted(sorted));
        System.out.println();

        // 测试负数
        int[] arrNeg = {-5, -1, -10, 0, 5, 3, -3};
        System.out.println("含负数数组：" + Arrays.toString(arrNeg));
        int[] sortedNeg = sortWithNegative(arrNeg);
        System.out.println("排序结果：" + Arrays.toString(sortedNeg));
        System.out.println();

        // 测试稳定性
        Student[] students = {
            new Student(85, "张三"),
            new Student(90, "李四"),
            new Student(85, "王五"),
            new Student(90, "赵六"),
            new Student(85, "孙七")
        };
        System.out.println("原始学生顺序：" + Arrays.toString(students));
        Student[] sortedStudents = sortStudentsByScore(students, 80, 95);
        System.out.println("排序后顺序：" + Arrays.toString(sortedStudents));
        System.out.println("稳定性验证（相同分数保持原顺序）：张三在孙七前？" + 
            (findIndex(sortedStudents, "张三") < findIndex(sortedStudents, "孙七")));
        System.out.println();

        // 性能对比
        performanceComparison();
    }

    private static int findIndex(Student[] arr, String name) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i].name.equals(name)) return i;
        }
        return -1;
    }
}

稳定性分析

计数排序的稳定性来源于从后向前遍历原数组的策略。当遇到相同值的元素时，后出现的元素会被先放置到输出数组中靠后的位置，从而保持相对顺序不变。

以 [85-张三, 85-王五, 85-孙七] 为例：
1. 累积计数后，85对应的位置范围为1-3
2. 从后向前遍历，孙七先被放到位置3
3. 然后是王五放到位置2
4. 最后是张三放到位置1
5. 最终顺序为 [85-张三, 85-王五, 85-孙七]，保持了原始顺序

复杂度分析

适用场景与局限性

适用场景

• 小范围整数排序：如年龄（0-150）、考试分数（0-100）
• 作为基数排序的子程序：基数排序利用计数排序对每一位进行稳定排序
• 需要稳定排序的场景：如多关键字排序的次级排序

局限性

• 仅适用于整数或有限离散值
• 空间开销大：当k远大于n时，空间效率低
• 不适合大范围数据：如32位整数范围太大

与快速排序对比

总结

计数排序通过巧妙的计数和累积策略，突破了比较排序O(n log n)的下界限制，在小范围整数排序场景下具有显著的性能优势。理解计数排序有助于掌握更高级的基数排序和桶排序算法。