C语言计数排序详解（零基础掌握线性时间排序算法）

计数排序的实现步骤

1. 找出待排序数组中的最大值和最小值，确定计数数组的大小。
2. 创建一个计数数组 count[]，长度为 (max - min + 1)，初始化为 0。
3. 遍历原数组，对每个元素 arr[i]，执行 count[arr[i] - min]++。
4. 对计数数组进行累加（可选，用于稳定排序）。
5. 根据计数数组重建排序后的结果数组。

C语言实现代码

下面是一个完整的 C语言计数排序实现示例：

#include <stdio.h>#include <stdlib.h>// 计数排序函数void countingSort(int arr[], int n) {    // 步骤1：找到最大值和最小值    int max = arr[0], min = arr[0];    for (int i = 1; i < n; i++) {        if (arr[i] > max) max = arr[i];        if (arr[i] < min) min = arr[i];    }    int range = max - min + 1;    int *count = (int *)calloc(range, sizeof(int));    int *output = (int *)malloc(n * sizeof(int));    // 步骤2：统计每个元素出现的次数    for (int i = 0; i < n; i++) {        count[arr[i] - min]++;    }    // 步骤3：将计数数组转换为位置索引（可选，用于稳定排序）    for (int i = 1; i < range; i++) {        count[i] += count[i - 1];    }    // 步骤4：从后往前填充输出数组（保证稳定性）    for (int i = n - 1; i >= 0; i--) {        output[count[arr[i] - min] - 1] = arr[i];        count[arr[i] - min]--;    }    // 步骤5：将排序结果复制回原数组    for (int i = 0; i < n; i++) {        arr[i] = output[i];    }    free(count);    free(output);}// 测试函数int main() {    int arr[] = {4, 2, 2, 8, 3, 3, 1};    int n = sizeof(arr) / sizeof(arr[0]);    printf("排序前: ");    for (int i = 0; i < n; i++) {        printf("%d ", arr[i]);    }    countingSort(arr, n);    printf("\n排序后: ");    for (int i = 0; i < n; i++) {        printf("%d ", arr[i]);    }    printf("\n");    return 0;}

算法优缺点分析

优点：

• 时间复杂度低，为 O(n + k)，属于线性时间排序。
• 稳定排序（若实现得当）。

缺点：

• 仅适用于整数或可映射为整数的数据。
• 当数据范围 k 很大时，空间开销显著增加。
• 不适合浮点数或字符串排序。

适用场景

如果你正在学习 C语言排序教程，计数排序非常适合以下场景：

• 考试成绩排序（如 0~100 分）
• 年龄、月份等有限整数范围的数据
• 作为基数排序的子程序

总结

通过本教程，你已经掌握了 C语言计数排序 的基本原理与实现方法。作为一种高效的 线性时间排序 算法，它在特定场景下表现优异。建议你动手运行上述代码，修改测试数据，加深理解。继续学习更多 C语言排序教程，你将逐步构建扎实的算法基础！