计数排序顺序表的定义 c语言

计数排序是一种非基于比较的整数排序算法，它适用于元素值范围相对较小且有序的情况。在C语言中，如果我们有一个整数数组，我们可以利用这个性质快速地对元素进行排序。

**定义：**
假设我们要对整数序列`arr[]`进行计数排序，首先我们需要确定输入数组中的最大值`max_val`，然后创建一个大小为`max_val+1`的计数数组`count[]`。对于每个输入元素`num`，我们将`count[num]`加一，这个操作相当于统计了每个数字出现的次数。接着，我们遍历计数数组，将每个元素的位置累加到前一个元素位置上，形成新的累积分布数组。最后，通过原数组和累积分布数组，我们可以重构原始数据并按照正确的顺序存储。

例如：

void countingSort(int arr[], int n, int max_val) {
    int count[max_val + 1]; // 初始化计数数组
    for (int i = 0; i < n; i++) {
        count[arr[i]]++; // 统计各元素出现次数
    }
    
    for (int i = 1; i <= max_val; i++) {
        count[i] += count[i - 1]; // 累加得到累积分布
    }
    
    int output[n];
    for (int i = n - 1; i >= 0; i--) { // 从大到小处理
        output[count[arr[i]] - 1] = arr[i]; // 重建按顺序排列的数组
        count[arr[i]]--;
    }

    // 将结果复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}