🔥个人主页：@草莓熊Lotso
🎬作者简介：C++研发方向学习者
📖个人专栏： 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》
⭐️人生格言：生活是默默的坚持，毅力是永久的享受。
前言：今天这篇文章主要是想给大家分享一下计数排序，并且对前面实现过的排序算法的时间复杂度，空间复杂度，稳定性进行一个归纳总结。话不多说，我们直接进入正文内容。
一.计数排序计数排序（Counting Sort）又称为鸽巢原理，是一种非比较型的线性时间排序算法，适用于 输入数据范围明确且较窄的场景。核心思想是通过“统计每个值的出现次数”，直接确定元素的最终位置，跳过耗时的比较操作。
核心步骤：1. 确定数据范围
遍历数组，找到最大值 max 和最小值 min，计算数据范围 range = max - min + 1。
（目的：创建合适大小的计数数组，避免空间浪费）
2. 统计元素出现次数
创建计数数组 count（长度为 range），注意count数组的初始化(开辟时用calloc或者后续用memset)，遍历原数组，将每个元素 arr[i] 映射到 count[arr[i] - min]（减去 min 是为了处理包含负数的情况，一定要用arr[i]-min），统计每个值的出现次数。
3. 将count数组中的数据排序还原到原数组中
定义一个索引变量index，用于记录原数组arr中即将写入数据的位置。遍历count数组(从0开始，然后小于 代码实现：代码语言：javascript复制//非比较排序--计数排序 void CountSort(int* arr, int n) { //找最大最小值确定范围 int min = arr[0]; int max = arr[0]; for (int i = 0; i < n; i++) { if (arr[i] < min) { min = arr[i]; } if (arr[i] > max) { max = arr[i]; } } int range = max - min + 1; int* count = (int*)malloc(sizeof(int) * range); if (count == NULL) { perror("malloc fail!"); exit(-1); } //对count初始化，可以用memset也可以前面申请空间的时候使用calloc memset(count, 0, sizeof(int) * range); //统计次数，映射，下标为arr[i]-min for (int i = 0; i < n; i++) { count[arr[i] - min]++; } //排序 int index = 0; //用range就可以了 for (int i = 0; i < range; i++) { while (count[i]--) { arr[index++] = i + min;//这里需要用i+min } } }test.c： 代码语言：javascript复制#include"Sort.h" void PrintArr(int* arr, int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } void test1() { int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 }; int size = sizeof(a) / sizeof(a[0]); printf("排序前:"); PrintArr(a, size); //直接插入排序 //InsertSort(a, size); //希尔排序 //ShellSort(a, size); //直接选择排序 //SelectSort(a, size); //堆排序 //HeapSort(a, size); //冒泡排序 //BubbleSort(a, size); //快速排序 //QuickSort(a, 0, size - 1); //非递归快速排序 //QuickSortNoare(a, 0, size - 1); //快速排序进阶版 //QuickSortMore(a, 0, size - 1); //归并排序 //MergeSort(a, size); //非递归实现归并排序 //MergeSortNore(a, size); //非比较排序--计数排序 CountSort(a, size); printf("排序后:"); PrintArr(a, size); } int main() { test1(); return 0; }--测试完成，打印没有问题，升序排序正确，退出码为0 计数排序的特性： 计数排序在数据范围集中时，效率很高，但是适用范围以及场景有限。时间复杂度：O(n+range)空间复杂度：O(range)稳定性：稳定 二.排序算法复杂度及稳定性分析稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。 各排序算法对比表： --其中冒泡排序，直接插入排序，归并排序是稳定的，这里就不过多介绍了，我们主要通过一些特例来看下那些不稳定的排序算法。至于时间复杂度和空间复杂度，博主大部分都在前面的博客中分享过了。 1.直接选择排序： 2.希尔排序： 3.堆排序： 4.快速排序： --前面一直没给大家展示过Sort.h文件，在这里给大家看一看 代码语言：javascript复制#pragma once #include #include #include //插入排序 //1)直接插入排序 void InsertSort(int* arr, int n); //2)希尔排序 void ShellSort(int* arr, int n); //选择排序 //1)直接选择排序 void SelectSort(int* arr, int n); //2)堆排序 void HeapSort(int* arr, int n); //交换排序 //1)冒泡排序 void BubbleSort(int* arr, int n); //2)快速排序 void QuickSort(int* arr, int left, int right); //快速排序非递归版本 void QuickSortNoare(int* arr, int left, int right); //快速排序进阶版本 void QuickSortMore(int* arr, int left, int right); //归并排序--主函数里面不递归，所以可以先不传left和right void MergeSort(int* arr, int n); //非递归实现归并排序 void MergeSortNore(int* arr, int n); //非比较排序--计数排序 void CountSort(int* arr, int n);往期回顾： 【数据结构初阶】--排序(一)：直接插入排序，希尔排序 【数据结构初阶】--排序(二)--直接选择排序，堆排序 【数据结构初阶】--排序(三)：冒泡排序，快速排序 【数据结构初阶】--排序(四)：归并排序 结语：本篇博客就到此结束了，后续应该还会更新一篇归并排序的进阶，然后就正式进入C++的学习了。我们数据结构初阶讲这些数据结构都是用C语言实现的，还有些比较难的数据结构在后续C++的学习中我们也会接触到，但是利用C++来实现就方便很多了，如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持。