计数排序

计数排序是一种非比较的排序算法，它的时间复杂度是O(n+k)，其中n是待排序数组的长度，k是数组中的最大值。计数排序的基本思想是，对于每个输入元素x，确定小于等于x的元素个数，然后把x放在输出数组中对应的位置上。为了实现这个过程，需要一个额外的数组C，用来存储每个元素出现的次数，以及一个累加数组D，用来存储每个元素在输出数组中的位置。计数排序的步骤如下：

1. 找出待排序数组A中的最大值和最小值，确定数组C和D的长度为k+1，其中k是最大值和最小值的差。
2. 遍历数组A，对于每个元素A[i]，将C[A[i]]加一，表示A[i]出现了一次。
3. 遍历数组C，对于每个元素C[j]，将D[j]赋值为C[0]到C[j-1]的和，表示小于等于j的元素个数。
4. 反向遍历数组A，对于每个元素A[i]，将其放在输出数组B中的第D[A[i]]个位置上，并将D[A[i]]减一，表示该位置已经被占用。
5. 返回输出数组B作为排序结果。

下面是一个用Java实现的计数排序算法的示例代码：

public class CountingSort {
    public static int[] sort(int[] arr) {
        //找出数组中的最大值和最小值
        int max = arr[0];
        int min = arr[0];
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
            if (num < min) {
                min = num;
            }
        }
        //确定数组C和D的长度
        int k = max - min;
        int[] C = new int[k + 1];
        int[] D = new int[k + 1];
        //统计每个元素出现的次数
        for (int num : arr) {
            C[num - min]++;
        }
        //计算每个元素在输出数组中的位置
        for (int i = 1; i <= k; i++) {
            D[i] = D[i - 1] + C[i - 1];
        }
        //反向填充输出数组
        int[] B = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            B[D[arr[i] - min]] = arr[i];
            D[arr[i] - min]--;
        }
        //返回排序结果
        return B;
    }

    public static void main(String[] args) {
        //测试数据
        int[] arr = {5, 3, 7, 2, 9, 1, 4, 6, 8};
        //打印原始数组
        System.out.println("原始数组：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
        //调用计数排序算法
        arr = sort(arr);
        //打印排序后的数组
        System.out.println("排序后的数组：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}