计数排序

计数排序（Counting Sort）是一种非比较排序算法，可以在线性时间复杂度（O(n)）内对一定范围内的整数数据进行排序。计数排序不是基于比较的排序算法，而是通过统计元素出现次数来实现排序。它的基本思想是对于给定的输入序列中的每个元素x，确定该序列中值小于x的元素的个数，利用这个信息将x直接放到它最终的输出位置上。计数排序需要一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。

以下是计数排序的C语言实现：

#include <stdio.h>

void countingSort(int arr[], int n, int max) {
    int count[max + 1]; // 用于统计待排序序列中每个元素的个数
    int output[n]; // 存储排序后的结果
    int i;

    // 将 count 数组中的所有元素初始化为0
    for (i = 0; i <= max; ++i) {
        count[i] = 0;
    }

    // 统计待排序序列中每个元素的个数
    for (i = 0; i < n; ++i) {
        ++count[arr[i]];
    }

    // 对 count 数组中的元素进行累加
    for (i = 1; i <= max; ++i) {
        count[i] += count[i - 1];
    }

    // 将待排序序列中的元素放到 output 数组中
    for (i = n - 1; i >= 0; --i) {
        output[count[arr[i]] - 1] = arr[i];
        --count[arr[i]];
    }

    // 将排序后的结果赋值给原始数组
    for (i = 0; i < n; ++i) {
        arr[i] = output[i];
    }
}

int main() {
    int arr[] = {6, 3, 9, 2, 7, 8, 4, 5, 1, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max = arr[0];
    int i;

    // 找出待排序序列中的最大值
    for (i = 1; i < n; ++i) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }

    countingSort(arr, n, max);

    // 输出排序后的结果
    for (i = 0; i < n; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}