【数据结构初阶】--排序(五)--计数排序，排序算法复杂度对比和稳定性分析

🔥个人主页：@草莓熊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开始，然后小于<range)，根据count[i]统计到的个数进行循环，循环次数等于该值出现的次数，将数组的原始数据值放入arr原始数组中(对应原始值一定是i+min)

代码实现：

//非比较排序--计数排序void CountSort(int* arr, int n){//找最大最小值确定范围int min = arr[0]; int max = arr[0];for (int i = 0; i < n; 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也可以前面申请空间的时候使用callocmemset(count, 0, sizeof(int) * range);//统计次数，映射，下标为arr[i]-minfor (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：

#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文件，在这里给大家看一看

#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和rightvoid MergeSort(int* arr, int n);//非递归实现归并排序void MergeSortNore(int* arr, int n);//非比较排序--计数排序void CountSort(int* arr, int n);

往期回顾：

【数据结构初阶】--排序(一)：直接插入排序，希尔排序

【数据结构初阶】--排序(二)--直接选择排序，堆排序

【数据结构初阶】--排序(三)：冒泡排序，快速排序

【数据结构初阶】--排序(四)：归并排序

结语：本篇博客就到此结束了，后续应该还会更新一篇归并排序的进阶，然后就正式进入C++的学习了。我们数据结构初阶讲这些数据结构都是用C语言实现的，还有些比较难的数据结构在后续C++的学习中我们也会接触到，但是利用C++来实现就方便很多了，如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持。