这个用来测试代码的对比排序性能的代码博主还是放在下面，大家可以对比一下各种排序算法的运行时间，从而对不同排序方法的时间复杂度有更加直观地认识：
代码演示：
代码语言：javascript复制//测试排序的性能对比
void TestOP()
{
srand(time(0));
const int N = 100000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
int* a7 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a1[i];
}
//begin和end的时间差就是
int begin1 = clock();
InsertSort(a1, N);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
int begin3 = clock();
SelectSort(a3, N);
int end3 = clock();
int begin4 = clock();
HeapSort(a4, N);
int end4 = clock();
int begin5 = clock();
QuickSort(a5, 0, N - 1);
int end5 = clock();
int begin6 = clock();
MergeSort(a6, N);
int end6 = clock();
int begin7 = clock();
BubbleSort(a7, N);
int end7 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("QuickSort:%d\n", end5 - begin5);
printf("MergeSort:%d\n", end6 - begin6);
printf("BubbleSort:%d\n", end7 - begin7);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
}目录正文
二. 非比较排序
一、计数排序（鸽巢原理）
1、概念
2、注意
（1）具体步骤
（2）计数排序的逻辑
（3）coust数组如何确定
3、代码实现
4、计数排序的特性
三. 排序算法复杂度及稳定性分析
一、概念
结尾
正文二. 非比较排序一、计数排序（鸽巢原理）1、概念 计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
2、注意（1）具体步骤 1）统计相同元素出现次数；
2）根据统计的结果将序列回收到原来的序列中。
（2）计数排序的逻辑（3）count数组如何确定也就是说：我们只需要开辟10个空间就可以把原数组中数据存储重复的次数保存在count里面。
前面我们还没有用到映射，所以{6,1,2,9,4,2,4,1,4}这个序列，虽然9+1-1=9，应该创建9个空间，但因为前面还没有提到映射，故还是创建了10个空间，映射之后是9个没错。
3、代码实现代码演示：
代码语言：javascript复制//非比较排序——计数排序
void CountSort(int* arr, int n)
{
//找min max
int min = arr[0], max = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] < min)
{
min = arr[i];
}
if (arr[i] > max)
{
max = arr[i];
}
}
//确定count数组的大小 max-min+1
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * (range));
if (count == NULL)
{
perror("malloc fail");
exit(1);
}
//对count初始化：calloc memset
memset(count, 0, sizeof(int) * (range));
for (int i = 0; i < n; i++)
{
count[arr[i] - min]++;
}
//将count数组中的数据还原到原数组中
int index = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
arr[index++] = i + min;
}
}
}时间复杂度：O(N + range) 。
4、计数排序的特性计数排序的特性：
1、计数排序在数据范围集中时，效率很高，但是适用范围及场景有限；
2、时间复杂度：O(N + range)；
3、空间复杂度：O(range)；
4、稳定性：稳定。
这个时间复杂度O(N + range)要比我们之前的这几种排序的时间复杂度高很多，所以说效率很高。
注意：关于这里的第一条特性，我们可以举个例子——
比如，待排序数组只有1和10000,1和10000这就属于数据范围非常分散的，不符合计数排序的特性，这么分散的数据就超出了计数排序的适用范围。
三. 排序算法复杂度及稳定性分析一、概念 稳定性的概念文绉绉的，看了并不好懂：
我们举这样一个例子：
这里有两个3，我们经过排序，原数组中下标为 i 的3跑到了在原数组在它后面的下标为 j 的3的后面，这个就叫做不稳定，反过来，如果下标顺序没有改变，就是稳定。
上面成绩的例子就很好地说明了稳定性的重要性， 同样是95分的两名同学，不稳定即先交卷的反而排在后交卷的那位95分的同学后面。
接下来我们来看这个——
这样将会是递归进行n次，时间复杂度就不好了，我们要取中间，这样就是logn次。
结尾 到这里，数据结构与算法初级阶段的内容我们就已经全部介绍完了！当然还不急着完结撒花！博主还会更新一些作为加餐，如果大家学有余力的话，可以去看看啦！比如快速排序里面的
往期回顾：
【数据结构与算法】数据结构初阶：详解排序（三）——归并排序：递归版本和非递归版本
【数据结构与算法】数据结构初阶：详解排序（二）——交换排序中的快速排序
【数据结构与算法】数据结构初阶：详解排序（一）——插入排序、选择排序以及交换排序中的冒泡排序
本期内容需要回顾的C语言知识如下面的截图中所示（指针博主写了6篇，列出来有水字数嫌疑了，就只放指针第六篇的网址，博主在指针（六）把指针部分的前五篇的网址都放在【往期回顾】了，点击【传送门】就可以看了）。
大家如果对前面部分的知识点印象不深，可以去上一篇文章的结尾部分看看，博主把需要回顾的知识点相关的博客的链接都放在上一篇文章了，上一篇文章的链接博主放在下面了：
【数据结构与算法】数据结构初阶：详解顺序表和链表（三）——单链表（上）
结语：本篇文章到这里就结束了，对数据结构的排序知识感兴趣的友友们可以在评论区留言，博主创作时可能存在笔误，或者知识点不严谨的地方，大家多担待，如果大家在阅读的时候发现了行文有什么错误欢迎在评论区斧正，再次感谢友友们的关注和支持！