【数据结构初阶】--排序(五)--计数排序，排序算法复杂度对比和稳定性分析
🔥个人主页：@草莓熊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] < 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也可以前面申请空间的时候使用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<stdio.h>
#include<stdlib.h>
#include<string.h>//插入排序
//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++来实现就方便很多了，如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持。