数据结构八大排序，你掌握了哪几大

文章目录

开篇一览

排序时间复杂度最好情况最坏情况空间复杂度稳定性直接插入排序O(N2)O(N)O(N2)O(1)稳定希尔排序O(NlogN)~O(N2)O(N1.25)O(N2)O(1)不稳定交换排序O(N2)O(N2)O(N2)O(1)不稳定

堆排序

O(NlogN)O(NlogN)O(NlogN)O(1)不稳定冒泡排序O(N2)O(N)O(N2)O(1)稳定

快速排序

O(NlogN)O(NlogN)O(N2)O(logN)~O(N)不稳定

归并排序

O(NlogN)O(NlogN)O(NlogN)O(N)稳定计数排序O(max(N,范围))O(max(N,范围))O(max(N,范围))O(范围)不稳定
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。本篇文章都是按升序对8个排序进行讲解。

排序除了复杂度外，还有稳定性。
稳定性：判断待排序数组中相同的值在排序后相对位置是否发生变化，可能变化就不稳定，可以保证不发生变化就是稳定。

接口

//交换函数voidSwap(int* pa,int* pb);// 直接插入排序voidInsertSort(int* a,int n);//希尔排序voidShellSort(int* a,int n);//选择排序voidSelectSort(int* a,int n);//向下调整voidAdjustDown(int* a,int parent,int n);//堆排序voidHeapSort(int* a,int n);//冒泡排序voidBubbleSort(int* a,int n);//快排voidQuickSort(int* a,int left,int right);//hoare版intPartSort1(int* a,int left,int right);//挖坑法intPartSort2(int* a,int left,int right);//前后指针版本intPartSort3(int* a,int left,int right);//快排非递归voidQuickSortNoR(int* a,int left,int right);//归并排序voidMerGeSort(int* a,int n);//归并非递归voidMerGeSortNoR(int* a,int n);//计数排序voidCountSort(int* a,int n);

直接插入排序

基本思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

单趟排序：
实际上我们玩扑克牌时，就用到了插入排序的思想。想象一下是如何将7插入到已经排好序的这五张牌中的。
数组arr中除最后一个元素arr[i]外已经有序，将有序数组最后一个元素arr[i-1]开始到arr[0]依次与arr[i]比较，遇到比arr[i]大的就右移一格，遇到比arr[i]小的直接将arr[i]插入到该元素后面

完整过程：当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，重复单趟排序直到数组最后一个元素插入后终止

//将数组a中的n个数据排序voidInsertSort(int* a,int n){//有序数组最后位置从0开始，逐渐排好序逐渐增加//当插入到最后一个元素时，插入元素下标为n-1//所以有序数组最后位置下标要<n-1for(int i =0; i < n-1; i++){int end = i;int x = a[end +1];//插入的值while(end >=0){if(a[end]> x){
                a[end +1]= a[end];--end;}elsebreak;}//循环终止有两种情况：//1.遇到比x小的，直接插入到该元素后面//2.end=-1时，直接插入到数组起始位置
        a[end +1]= x;}}

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高O(N)，几乎每次只比较一次不用挪动数据（最好情况）
2. 元素集合接近逆序时最坏情况，时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

希尔排序

希尔排序法又称缩小增量法。在直接插入排序的思想上进行优化，且优化效果十分明显。

基本思想是：先选定一个整数gap，gap每次排序之前都会减小，把待排序文件中所有记录分成gap组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后重复上述分组和排序的工作。当gap=1时，所有记录在统一组内排好序。

1. 当gap>1时进行分组预排，让数组接近有序
2. gap=1时就是直接插入排序

假设gap=3，数组分成3组（蓝色、红色、粉色三组），距离为3的为一组，按直接插入排序的思想分别对每组比较
ps：10个数时gap初始值一般是取5或4，这里gap只取成了3，进行预排

//希尔排序voidShellSort(int* a,int n){int gap = n;while(gap >1){//gap常见的两种取值//gap /= 2;//gap==1时就是直接插入排序了
        gap = gap /3+1;//多组并排//类比直接插入排序的思想，直接插入排序的gap=1for(int i =0; i < n - gap; i++){int end = i;int x = a[end + gap];//直接插入排序是+1，这里是+gapwhile(end >=0){if(a[end]> x){
                    a[end + gap]= a[end];
                    end -= gap;//直接插入排序是-1，这里是-gap}elsebreak;}
            a[end + gap]= x;}}}

release版本下：排100万个数时，直接插入排序大概花了2分钟，而希尔排序只要0.1秒，希尔排序对直接排序优化效果十分明显

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化，且优化效果十分明显。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，接近有序时直接插入排序的时间复杂度:O(N)，O(N)级别就是排序的天花板了
3. gap约大预排越快，但预排后越不接近有序，gap越小预排越慢，但预排后约接近有序，所以需要合理控制好gap。一般取gap=gap/2(最后gap一定会=1)，或是gap=gap/3+1（因为gap/3有可能直接除到0所以要+1）
4. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，暂时认为是O(n1.25)
5. 稳定性：不稳定

选择排序

基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
动图演示每次取的是最小的
还可以优化一下，每次选两个数，一个最大的一个最小的

voidSwap(int* pa,int* pb){int tmp =*pa;*pa =*pb;*pb = tmp;}voidSelectSort(int* a,int n){int end = n -1;int begin =0;//一前一后，不断缩小范围while(begin < end){int maxi = begin, mini = begin;for(int i = begin; i <= end; i++){if(a[maxi]< a[i])
                maxi = i;if(a[mini]> a[i])
                mini = i;}//特殊情况if(begin == maxi)
            maxi = mini;Swap(&a[begin],&a[mini]);Swap(&a[end],&a[maxi]);++begin;--end;}}

特殊情况，begin与maxi咋同一位置，因为我们是先交换begin与mini位置的值，所以maxi位置的值就是最小的，mini位置的值是最大的，所以可以把mini的值为maxi

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率很低，实际中很少使用
2. 时间复杂度：O(N2)（怎么优化都是O(N2）
3. 空间复杂度：O(1)
4. 稳定性：不稳定

堆排序（重点）

堆排序是选择排序的一种，它是通过堆来进行选择数据。
基本思想：从最后一个非叶子节点开始到根节点依次向下调整

1.排升序建大堆，排降序建小堆。
参考堆删除思想，是将堆顶与堆尾的数据交换后再–size也就pop掉堆顶的元素了，所以只需要保证交换后堆尾的数最大（这样最大的数就在最后），也就是交换之前堆顶的数最大，这就是大堆的结构。所以排升序要建大堆，同理排降序建小堆

2.用向下调整建堆的时间复杂度是O(N)，而用向上调整建堆的时间复杂度是O(NlogN)，所以向下调整建堆更好，同时排序也需要用到向下调整。
单次向下调整时间复杂度O(logN)高度次

我的这篇文章已经详细讲解了堆排序和相关复杂度证明，这里就不在赘述了
堆排序

堆排序特性总结：

1. 时间复杂度：O(N*logN)
2. 空间复杂度：O(1)
3. 稳定性：不稳定

//向下调整--升序建大堆voidAdjustDown(int* a,int parent,int n){int child = parent *2+1;//左孩子while(child < n){if(child +1< n && a[child +1]> a[child])++child;if(a[child]> a[parent]){Swap(&a[parent],&a[child]);
            parent = child;
            child = parent *2+1;}elsebreak;}}//堆排序voidHeapSort(int* a,int n){int lastparent =(n -1-1)/2;//建大堆，从最后一个非叶子节点开始向下调整--时间复杂度O(N)for(int i = lastparent; i >=0; i--){AdjustDown(a, i, n);}//将大数逐渐右移，堆中元素个数逐渐减小int end = n -1;while(end >0)//时间复杂度O(NlogN){Swap(&a[0],&a[end]);AdjustDown(a,0, end);--end;}}

冒泡排序

冒泡排序相必大家已经很熟悉了，冒泡排序是一种交换排序
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。
交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

voidBubbleSort(int* a,int n){for(int i =0; i < n -1; i++){int flag =1;for(int j =1; j < n - i; j++){if(a[j -1]> a[j]){Swap(&a[j -1],&a[j]);
                flag =0;}}//没有发生交换就证明已经有序了if(flag ==1)break;}}

冒泡排序的特性总结：

1. 时间复杂度：O(N^2)
2. 空间复杂度：O(1)
3. 稳定性：稳定

对直接插入排序、选择排序、冒泡排序分析：
选排肯定是最差的，每次不管取一个数还是两个数，时间复杂度都是O(N2)，冒泡和直接插入综合而言，直接插入是更优的，因为直接插入排序不需要完整的走完每趟，只要发生就换就会终止，而冒泡是需要一趟走完的

快速排序（重点）

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。
基本思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

hoare版本

hoare版本是Hoare最开始提出的一种版本

单趟排序：

1. 一般选数组最左边或最右边的值作key。选中间的值操作麻烦，边上的值更好操作
2. 用left和right分别从数组左右两边向中间遍历数组
3. v左边left找比key大的值，右边right找比key小的值（等于时不做处理），然后左右值交换
4. 反复循环，直到left和right相遇时终止
5. 将相遇位置的值与key交换，这样比key大的值都到右边了，比key小的值都到左边了

选左边的值作key时，右边先走-----相遇时的值比key小
选右边的值作key时，左边先走----相遇时的值比key大
单趟排序后的目标是：左边的值比key小，右边的值比key大

选左边的值作key时，为什么要让右边的先走？
因为左边是找比key大的值，右边是找比key小的值，相遇前进行最后一次交换后，当前left的值比key小，right的值比key大，如果让左边先走，那么相遇时的值(right所在位置的值)就比key大了，最后与key交换后，最左边的值就比key大了。同理选右边的值作key时，左边先走

intPartSort1(int* a,int left,int right){//最左边作keyint keyi = left;while(left < right){//右边先走，找比key小的值while(left < right && a[right]>= a[keyi]){--right;}//左边再走，找比key大的值while(left < right && a[left]<= a[keyi]){++left;}Swap(&a[left],&a[right]);}//最后交换key与相遇位置的值Swap(&a[keyi],&a[left]);return left;}

整体排序：
第一趟排完后，key的左边都比它小，右边都比它大，这样如果key的左右子区间都有序了，整体也就有序了。采用分治思想，将一个大问题分治成最小子问题，我们分别对[left,key-1]和[key+1,right]排序重复单趟的操作，当区间只有一个值时这个子区间就是有序的了

//快排--前序思想voidQuickSort(int* a,int left,int right){if(left >= right)return;int keyi =PartSort1(a, left, right);//[left,keyi-1] keyi [keyi+1,right]QuickSort(a, left, keyi -1);QuickSort(a, keyi +1, right);}

快排最好情况：最次从最左边或最右边取的key都是数组的中位数，单趟排序完交换后，key就到数组中间了，类似于叉树结构，单趟时间复杂度O(N)、高度logN，时间复杂度是(NlogN)

快排最坏的情况

：当数组接近有序时，最左边的值可能是最小的，选最左边作key，右边先走找比key小的值，那么结束条件就是right一直走到最左边，N*(N-1)*(N-2)…时间复杂度O(N2)。

解决快排面对有序情况选key的问题：

• 随机选取key（一切随缘）
• 三数取中（选出left，mid，right三数中次大的值作key），面对最坏的情况（数组接近有序），仍然可以选到中位数作key，变成最好的情况，这样就解决了快排时数组接近有序的问题

//三数取中intGetMidIndex(int* a,int left,int right){int mid = left +(right - left)/2;if(a[left]> a[mid]){if(a[left]> a[right]){if(a[mid]> a[right])return mid;elsereturn right;}elsereturn right;}else{if(a[mid]> a[right]){if(a[left]> a[right])return left;elsereturn right;}elsereturn mid;}}intPartSort1(int* a,int left,int right){//三数取中int mid =GetMidIndex(a, left, right);Swap(&a[left],&a[mid]);//最左边作keyint keyi = left;while(left < right){//右边先走，找比key小的值while(left < right && a[right]>= a[keyi]){--right;}//左边再走，找比key大的值while(left < right && a[left]<= a[keyi]){++left;}Swap(&a[left],&a[right]);}//最后交换key与相遇位置的值Swap(&a[keyi],&a[left]);return left;}

挖坑法

挖坑法和hoare版的思想类似

基本思想：

1. 选一个值作key保存，一般选最左边或最右边作key，并将key所在位置作为初始坑位pit
2. 选左边作key，右边先走，找比key小的值，并将找到的值填入坑中，然后作为新的坑位
3. 再让左边走，找比key大的值，并将找到的值填入坑中，然后作为新的坑位
4. 反复循环，直到left和right相遇时终止
5. 当left和right相遇时，将最开始保存的值key填入坑位
6. 此时key的左边都比它小，右边都比它的，在分别对key的左右子区排序，重复上面步骤

//挖坑法intPartSort2(int* a,int left,int right){//三数取中int mid =GetMidIndex(a, left, right);Swap(&a[left],&a[mid]);int key = a[left];int pit = left;while(left < right){//右边先走，找比key小的值while(left < right && a[right]>= key){--right;}
        a[pit]= a[right];//填入坑位
        pit = right;//变成新的坑//左边再走，找比key大的值while(left < right && a[left]<= key){++left;}
        a[pit]= a[left];//填入坑位
        pit = left;//变成新的坑}//left和right相遇后，将key填入坑中
    a[pit]= key;return pit;}voidQuickSort(int* a,int left,int right){if(left >= right)return;int keyi =PartSort2(a, left, right);//[left,keyi-1] keyi [keyi+1,right]QuickSort(a, left, keyi -1);QuickSort(a, keyi +1, right);}

前后指针版本

前后指针版本相必于上面的两个版本要更好理解，快排通常是使用的这个版本实现的

基本思想：

1. 定义两个指针prev和cur（初始时cur=prev+1）
2. 一般选数组最左边或最右边的值作key
3. 选左边作key时 3.1 prev指向数组第一个数，cur指向数组第二个数 3.2 cur先走找比key小的值，然后++prev，再交换prev和cur位置的值 3.3 重复上面操作，直到cur遍历完数组后终止 3.4 最后交换key与prev位置的值
4. 选右边作key时 4.1 cur指向数组第一个数，prev在cur左边一格 4.2 cur先走找比key小的值，然后++prev，再交换prev和cur位置的值 4.3 重复上面操作，知道cur遍历完数组后终止 4.4 最后再++prev，交换key与prev位置的值
5. 此时key的左边都比它小，右边都比它的，在分别对key的左右子区排序，重复上面步骤

cur把小的值往左边推，prev把大的值往右边推。cur找比key小的，而prev是紧跟着cur或者紧跟着比key大的序列

intPartSort3(int* a,int left,int right){//三数取中int mid =GetMidIndex(a, left, right);Swap(&a[left],&a[mid]);//选最左边作keyint key = left;int prev = left, cur = prev +1;while(cur <= right){//cur先走，找比key小的值(prev和cur位置一样时就不用交换了)if(a[cur]< a[key]&&++prev != cur)Swap(&a[prev],&a[cur]);++cur;}Swap(&a[prev],&a[key]);return prev;}voidQuickSort(int* a,int left,int right){if(left >= right)return;int keyi =PartSort2(a, left, right);//[left,keyi-1] keyi [keyi+1,right]QuickSort(a, left, keyi -1);QuickSort(a, keyi +1, right);}

动图演示的大致思路和上面类似，只是有细微的差别，取最左边的值作key，初始条件是cur和prev都从第二个元素位置开始，cur找比key小的值且是先交换cur与prev位置的值，再++prev，最后是交换a[keyi]与a[–prev]位置的值

快排的小区间优化

采用递归实现有一个缺陷：因为每次递归都要建立栈帧，当递归的深度太深时就会栈溢出，快排的子区间划分类似于一颗二叉树结构，如果以满二叉树的高度h为例，总节点个数就是2h-1，而最后一层的节点个数是2h-1，几乎占了树的一半，那么最后一层递归调用的函数几乎占了快排递归调用的一半。
当分割到小区间时，就可以不用递归分割的思路让这段子区间有序，因为子区间是接近有序的，key的左边都比key小，右边都比key大，那么就可以用直接插入排序的非递归代替快排的递归，（对接近有序的数组，直接插入就是O(N))，这样可以有效减少递归调用的次数

voidQuickSort(int* a,int left,int right){if(left >= right)return;int keyi =PartSort3(a, left, right);//[left,keyi-1] keyi [keyi+1,right]if(right - left <10)//子区间的数小于11时，用直接插入排序对接近有序的子区间排序InsertSort(a + left, right - left +1);else{QuickSort(a, left, keyi -1);QuickSort(a, keyi +1, right);}}

虽然用三数取中解决了对接近有序序列排序的问题，同时小区间优化也大大减少了递归调用的次数，但当序列中都是接近重复的数时，还是无法解决栈溢出问题，且快排时间复杂度是最坏情况O(N2)，这是快排的一个缺陷。所以当序列中的数接近重复时不建议使用快排，用直接插入排序也不错

当然想要解决栈溢出问题，就需要用非递归实现

快排的非递归实现

对简单的递归可以直接用循环代替，但是快排的非递归需要

借助栈模拟实现

。以前后指针版本为例，每次递归调用PartSort3都要建立新的函数栈帧，形参中

a的值不变

，只有

left和right的值在变化

，所以我们可以将每次变化的left和right放入栈中，因为栈是先进后出的，也符合递归的思想：不断往下递推再回归。
ps：当然也可以用队列模拟实现，只是过程与递归的过程不同，类似层序遍历的实现思想
由于C语言没有标准模板库，所以需要自己实现一个stack，源码放在文末。

voidQuickSortNoR(int* a,int left,int right){
    ST st;StackInit(&st);//初始化//首先就将left和rightpush入栈StackPush(&st, left);//left先入后出栈StackPush(&st, right);//right后入先出栈//只要栈不为空就可以一直循环迭代while(!StackEmpty(&st)){int end =StackTop(&st);StackPop(&st);int begin =StackTop(&st);StackPop(&st);int keyi =PartSort3(a, begin, end);//[begin,keyi-1] keyi [keyi+1,end]//先入右区间，后排序，当区间的值只有一个或不存在时就不需要排序了if(keyi +1< end){StackPush(&st, keyi +1);StackPush(&st, end);}//后入左区间，先排序if(begin < keyi -1){StackPush(&st, begin);StackPush(&st, keyi -1);}}}

快排的特性总结：

1. 这么多排序只有它才敢叫快排，所以快速排序整体的综合性能和使用场景都是比较好的
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定

归并排序（重点）

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。
基本思想：
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

所以归并的前提是两个序列是有序的，实际上在刷链表题的时候就用到了归并的思想
将数组划分为左右区间[left,mid]、[mid+1,right]，然后区间不断划分，直到子区间被划分为只有一个数时，一个数肯定是有序的，然后对有序序列一一合并（下图的6和1合并、2和5合并…）、两两合并（1、6和2、5合并…）四四合并…让整体有序。

由于链表都是一个一个的节点链接起来的，空间不连续，排序时可以直接链接，而数组是一段连续的空间，对数组排序时，需要借助一个tmp数组，将排序后的子序列保存到tmp数组中，然后在拷贝到原数组。

//借助临时数组tmp对a数组[left,right]区间的数排序//用子函数_MerGeSort完成归并void_MerGeSort(int* a,int left,int right,int* tmp){if(left >= right)return;int mid = left +(right - left)/2;//[left,mid] [mid+1,right]区间不断分解_MerGeSort(a, left, mid, tmp);_MerGeSort(a, mid +1, right, tmp);//比较后合并到tmp数组int i = left;int begin1 = left, end1 = mid;int begin2 = mid +1, end2 = right;while(begin1 <= end1 && begin2 <= end2){if(a[begin1]< a[begin2])
            tmp[i++]= a[begin1++];else
            tmp[i++]= a[begin2++];}while(begin1 <= end1){
        tmp[i++]= a[begin1++];}while(begin2 <= end2){
        tmp[i++]= a[begin2++];}//将tmp拷贝到原数组for(int i = left; i <= right; i++){
        a[i]= tmp[i];}}voidMerGeSort(int* a,int n){int* tmp =(int*)malloc(sizeof(int)* n);_MerGeSort(a,0, n -1, tmp);free(tmp);
    tmp =NULL;}

归并的非递归实现

归并的递归可以直接用循环代替，直接跳到归并部分开始比较

需要注意边界条件。参考上面的递归，left>=right时就直接return了，所以begin1是不存在越界的，但end1、begin2和end2都可能存在越界

voidMerGeSortNoR(int* a,int n){int* tmp =(int*)malloc(sizeof(int)* n);int grp =1;//最开始一个数为一组while(grp < n){for(int i =0; i < n; i += grp *2){//左区间[i,i+grp-1]  右区间[i+grp,i+grp*2-1]int begin1 = i, end1 = i + grp -1;int begin2 = i + grp, end2 = i + grp *2-1;int index = begin1;//end1越界或者右区间不存在就不需要归并了if(end1 >= n || begin2 >= n)break;if(end2 >= n)//右区间存在仅end2越界，修正下标
                end2 = n -1;while(begin1 <= end1 && begin2 <= end2){if(a[begin1]< a[begin2])
                    tmp[index++]= a[begin1++];else
                    tmp[index++]= a[begin2++];}while(begin1 <= end1){
                tmp[index++]= a[begin1++];}while(begin2 <= end2){
                tmp[index++]= a[begin2++];}//将子区间在tmp的数据拷回原数组for(int j = i; j <= end2; j++){
                a[j]= tmp[j];}}
        grp *=2;}free(tmp);
    tmp =NULL;}

归并排序的特性总结：

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。所以当数据量特别大存储在文件中，内存中一次性无法加载完时，就可以通过快排和归并配合排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定

计数排序

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

基本思想：

1. 采用相对映射
2. 通过一个count数组统计各元素出现的次数
3. 根据conunt统计的结果完成排序

voidCountSort(int* a,int n){int min = INT_MAX, max = INT_MIN;//确定数据范围for(int i =0; i < n; i++){if(a[i]> max)
            max = a[i];if(a[i]< min)
            min = a[i];}int range = max - min +1;int* count =(int*)malloc(sizeof(int)* range);//计数数组if(count ==NULL){perror("malloc failed:");exit(-1);}memset(count,0,sizeof(int)* range);//初始化为零//统计每个数出现的次数for(int i =0; i < n; i++){
        count[a[i]- min]++;//通过相对映射记录该数出现的次数}int aindex =0;//通过下标的相对映射和出现的次数写入数组a中for(int i =0; i < range; i++){while(count[i]--){
            a[aindex++]= i + min;}}}

计数排序的特性总结：

1. 计数排序在数据范围集中时，效率很高。数据很集中时，可以认为时间复杂度O(N)，空间复杂度O(1)。但是适用范围及场景有限，只适合对非负整数排序，如果排序的数都是负数也还行，但有正有负或者是浮点数就不适合了。
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)
4. 稳定性：稳定

栈的源码

Stack.h

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>typedefint DataType;typedefstructStack{
    DataType* p;int top;int capacity;}ST;//栈初始化voidStackInit(ST* pc);//压栈voidStackPush(ST* pc, DataType x);//出栈voidStackPop(ST* pc);//获取栈顶元素值
DataType StackTop(ST* pc);//销毁栈voidStackDestroy(ST* pc);//判断栈是否为空boolStackEmpty(ST* pc);//确定栈中元素个数
DataType StackSize(ST* pc);

Stack.c

#define_CRT_SECURE_NO_WARNINGS1#include"Stack.h"#include"Stack.h"voidStackInit(ST* pc){assert(pc);

    pc->capacity = pc->top =0;//这里top取0，表示栈中元素个数
    pc->p =NULL;}voidStackPush(ST* pc, DataType x){assert(pc);//判断是否要扩容if(pc->capacity == pc->top){int newCapacity = pc->capacity ==0?4:2* pc->capacity;
        DataType* tmp =(DataType*)realloc(pc->p,sizeof(ST)* newCapacity);if(tmp ==NULL){printf("%s\n",strerror(errno));exit(-1);}
        pc->p = tmp;
        pc->capacity = newCapacity;}
    pc->p[pc->top]= x;
    pc->top++;}boolStackEmpty(ST* pc){assert(pc);return pc->top ==0;//栈为空返回true非零，不为空返回false零}voidStackPop(ST* pc){assert(pc &&!StackEmpty(pc));

    pc->top--;}
DataType StackTop(ST* pc){assert(pc &&!StackEmpty(pc));return pc->p[pc->top -1];}
DataType StackSize(ST* pc){assert(pc);return pc->top;}voidStackDestroy(ST* pc){assert(pc);free(pc->p);
    pc->p =NULL;
    pc->top = pc->capacity =0;}

以上就是数据结构常见的八大排序了，希望我的文章对你有所帮助，欢迎👍点赞 ，📝评论，🌟关注，⭐️收藏