一文彻底搞清楚数据结构之排序算法大揭秘
🔥承渊政道：个人主页
❄️个人专栏: 《C语言基础语法知识》《数据结构与算法初阶》
✨逆境不吐心中苦,顺境不忘来时路!🎬 博主简介:
前言:前面小编已经介绍完了关于遍历二叉树以及讲解了一些二叉树相关OJ算法题的解题思路,自此关于二叉树的内容已经介绍完了!接下来小编将要介绍一个新的内容–>排序算法,它又有什么作用呢?废话不多说,下面跟着小编的节奏🎵一起学习吧！
目录
1.排序的概念
排序是指将一个数据元素的任意序列按关键字的递增或递减次序重新排列起来,使其成为一个按关键字有序排列的序列.若按主关键字进行,则排序的结果将是唯一的;若排序按次关键字进行,则排序的结果可能不唯一.简单来说:所谓排序,就是使⼀串记录,按照其中的某个或某些关键字的⼤⼩,递增或递减的排列起来的操作.
排序可分为两类:内部排序和外部排序.内部排序是指将待排序数据元素完全放置在内存中进行排序的方法.外部排序是指因待排数据元素数量太大,排序过程中不仅需要使用内存,还要借助外部存储器来完成排序方法.
由于内存和外存在访问速度、特点上的不同,内部排序方法与外部排序方法的侧重点不同.这里主要介绍常用的内部排序方法,但有些方法也可用于外部排序,如归并排序.
1.1常见的排序算法
2.插入排序
直接插⼊排序是⼀种简单的插⼊排序法,其基本思想是:把待排序的记录按其关键码值的⼤⼩逐个插⼊到⼀个已经排好序的有序序列中,直到所有的记录插⼊完为⽌,得到⼀个新的有序序列 .实际中我们玩扑克牌时,就⽤了插⼊排序的思想
2.1直接插入排序(附动图)
直接插入排序是一种最简单的排序方法,它的基本思想是将待排数据元素插入到已排好序的有序表中,从而得到一个新的有序表.对于一个具有n个数据元素的序列,进行直接插入排序具体过程是(按关键字升序排列):
①将第1个数据元素看作一个已排好序的有序表.
②将第i(2≤i≤n)个数据元素的关键字K;依次与其前面数据元素的关键字Ki-1、Ki-2、…、K1进行比较,将所有关键字大于K;的数据元素依次向后移动一个位置,直到某个数据元素的关键字K;小于或者等于Ki时,将第i个数据元素插入到关键字为Kj的数据元素后面,即完成第i个数据元素的插入.
③ 经过n一1次插入操作后,所有数据元素构成一个按关键字值大小排列的有序序列.
当插⼊第i(i>=1)个元素时,前⾯的array[0],array[1],…,array[i-1] 已经排好序,此时⽤array[i]的排序码与 array[i-1],array[i-2],… 的排序码顺序进⾏⽐较,找到插⼊位置即将array[i]插⼊,原来位置上的元素顺序后移.
//直接插入排序voidInsertSort(int* arr,int n){for(int i =0; i < n -1; i++)// 循环控制“未排序元素”的选取{int end = i;// end：“已排序部分”的最后一个元素下标int tmp = arr[end +1];// tmp：当前要插入的“未排序元素”（已排序区的下一个元素）// 在“已排序部分”中找tmp的插入位置while(end >=0){if(arr[end]> tmp)// 如果已排序元素比tmp大{ arr[end +1]= arr[end];// 把该元素往后移一位（给tmp腾位置） end--;// 继续往前找更小的元素}else// 如果已排序元素 <= tmp，说明找到了插入位置{break;// 退出循环，准备插入tmp}} arr[end +1]= tmp;// 把tmp放到最终的插入位置}}直接插⼊排序的特性总结
元素集合越接近有序,直接插⼊排序算法的时间效率越⾼
时间复杂度：
最好情况(数组已升序): O(N)(只需遍历一次,无需移动元素–>小的数据在前,大的数据在后)
最坏情况(数组逆序): O(N2)(每个元素都要移动到最前面–>大的数据在前,小的数据在后)
空间复杂度:O(1)(原地排序,无需额外空间)
2.2希尔排序
希尔(Shell)排序是1959年由D.L.Shell在直接插入排序的基础上,提出的一种改进的排序方法.它的基本思想是:将待排序数据元素划分成若干个子序列,其中每个子序列由相隔某个“增量”的数据元素组成,然后对这些子序列分别进行直接插入排序,通过缩小“增量”对子序列进行调整.当整个序列基本有序时,对全部数据元素进行一次直接插入排序.因此,希尔排序也称为"缩小增量排序"(Diminishing Increment Sort).
对于一个具有n 个数据元素的序列,进行希尔排序的具体过程是:
①按选定增量dl(dl<n),将所有距离为d1的数据元素划分为一个子序列,对各个子序列进行直接插入排序.
②选定增量d2(d2<d1),对所有数据元素重新进行划分并对各子序列直接插入排序.
③重复以上操作,直到增量d=1,即将所有数据元素放在一个子序列中进行一次直接插入排序,最后得到所有数据元素按关键字有序排列的序列.
希尔排序法的基本思想是:先选定⼀个整数(通常是gap=n/3+1),把待排序⽂件所有记录分成各组,所有的距离相等的记录分在同⼀组内,并对每⼀组内的记录进⾏排序,然后gap=gap/3+1得到下⼀个整数,再将数组分成各组,进⾏插⼊排序,当gap=1时,就相当于直接插⼊排序.它是在直接插⼊排序算法的基础上进⾏改进⽽来的,综合来说它的效率肯定是要⾼于直接插⼊排序算法的.
//希尔排序voidShellSort(int* arr,int n){int gap = n;// gap初始化为数组长度（第一步的分组步长）while(gap >1){ gap = gap /3+1;// 对每组进行直接插入排序for(int i =0; i < n - gap; i++)// i控制“每组的起始位置”，避免end+gap越界{int end = i;// end：当前组“已排序部分”的最后一个元素下标int tmp = arr[end + gap];// tmp：当前要插入的“未排序元素”（组内下一个元素）while(end >=0){if(arr[end]> tmp)// 已排序元素比tmp大 → 往后挪gap位{ arr[end + gap]= arr[end]; end -= gap;// 组内往前跳gap位，继续比较}else// 找到插入位置，退出循环{break;}} arr[end + gap]= tmp;// 把tmp插入到组内的正确位置}}}希尔排序的特性总结:
希尔排序是对直接插⼊排序的优化.
1️⃣当gap >1时都是预排序,⽬的是让数组更接近于有序.
2️⃣当gap == 1时(直接插入排序),数组已经接近有序的了,这样就会很快.这样整体⽽⾔,可以达到优化的效果.
3️⃣gap一般都是除2或者除3.gap/2 导致循环次数增多,+1 是为了保证最后一次gap一定会变成1.
4️⃣第一趟排序到第二趟排序,存在大的数据在前,小的数据在后,但是每组比较的数据量要小.
5️⃣第三趟排序,小的数据在前面分组排序的过程中已经放到前面去了大的数据已经放到后面去了
2.3希尔排序的时间复杂度计算
希尔排序的时间复杂度估算
外层循环:外层循环的时间复杂度可以直接给出为:O(log2n)或者O(log3n),即O(logn)
内层循环：
假设⼀共有n个数据,合计gap组,则每组为 n g a p \frac{n}{gap} gapn个;在每组中,插⼊移动的次数最坏的情况下为:1 + 2 + 3 + … + ( n g a p \frac{n}{gap} gapn-1)).⼀共是gap组,因此:
总计最坏情况下移动总数为:gap ∗ [1 + 2 + 3 + … + ( n g a p \frac{n}{gap} gapn-1)]
gap取值有(以除3为例): n 3 \frac{n}{3} 3n n 9 \frac{n}{9} 9n n 27 \frac{n}{27} 27n… 2 1
1️⃣当gap为 n 3 \frac{n}{3} 3n时,移动总数为: n 3 \frac{n}{3} 3n∗(1 + 2) = n
2️⃣当gap为 n 9 \frac{n}{9} 9n时,移动总数为: n 9 \frac{n}{9} 9n∗(1 + 2 + 3 + … + 8) = n 9 \frac{n}{9} 9n ∗ 8 ( 1 + 8 ) 2 \frac{8(1+8)}{2} 28(1+8) =4n
3️⃣最后⼀躺,gap=1即直接插⼊排序,内层循环排序消耗为n通过以上的分析,可以画出这样的曲线图：
因此,希尔排序在最初和最后的排序的次数都为n,即前⼀阶段排序次数是逐渐上升的状态,当到达
某⼀顶点时,排序次数逐渐下降⾄n,⽽该顶点的计算暂时⽆法给出具体的计算过程
希尔排序时间复杂度不好计算,因为 gap 的取值很多,导致很难去计算,因此很多书中给出的希尔排序的时间复杂度都不固定.《数据结构(C语⾔版)》— 严蔚敏书中给出的时间复杂度为:
3.选择排序
选择排序的基本思想：
每⼀次从待排序的数据元素中选出最⼩(或最⼤)的⼀个元素,存放在序列的起始位置,直到全部待排序的数据元素排完.
3.1直接选择排序(附动图)
直接选择排序的基本思想是:通过关键字的比较,每次从待排序列中选出关键字最小的数据元素,将其与待排序列的第一个数据元素交换,直到全部数据元素都有序排列.
对于一个具有n个数据元素的序列,进行直接选择排序的具体过程是:
①进行第一趟排序时,用r[1]与其余n-1个数据元素比较,选出关键字最小的数据元素与r[1]交换.
②进行第二趟排序时,用r[2]与其余n-2个数据元素比较,选出关键字最小的数据元素与r[2]交换.
③依此类推,进行第i趟排序时,用r[i]与其余n-i个数据元素比较,选出关键字最小的数据元素与r[i]交换.共需进行i-1趟选择,直到所有数据元素有序排列为止.
1️⃣在元素集合array[i]–array[n-1]中选择关键码最⼤(⼩)的数据元素.
2️⃣若它不是这组元素中的最后⼀个(第⼀个)元素,则将它与这组元素中的最后⼀个(第⼀个)元素
3️⃣交换在剩余的 array[i]–arrayn-2集合中,重复上述步骤直到集合剩余1个元素
voidSwap(int* x,int* y){int tmp =*x;*x =*y;*y = tmp;}//直接选择排序voidSelectSort(int* arr,int n){int begin =0, end = n -1;while(begin < end){int maxi = begin;int mini = begin;for(int i = begin +1; i <= end; i++){if(arr[i]< arr[mini]){ mini = i;}if(arr[i]> arr[maxi]){ maxi = i;}}if(maxi == begin){ maxi = mini;}Swap(&arr[mini],&arr[begin]);Swap(&arr[maxi],&arr[end]); begin++; end--;}}直接选择排序的特性总结：
直接选择排序思考⾮常好理解,但是效率不是很好.实际中很少使⽤
时间复杂度:O(n2)(和普通选择排序一致,但循环次数减少约一半);
空间复杂度:O(1)(原地排序,仅用常数级临时变量);
比普通选择排序(每次只找一个最值)更高效,尤其对大数组更明显.
3.2堆排序
堆排序(Heapsort)是指利⽤堆积树(堆)这种数据结构所设计的⼀种排序算法,它是选择排序的⼀
种.它是通过堆来进⾏选择数据.需要注意的是排升序要建⼤堆,排降序建⼩堆.
我在⼆叉树之堆中已经介绍过堆排序,这⾥不再赘述–>直接上代码.
有兴趣可以看看之前的内容关于堆排序的文章内容
voidAdjustDown(HPDataType* arr,int parent,int n){int child = parent *2+1;//左孩子while(child < n){//大堆：<//小堆：>if(child +1< n && arr[child]< arr[child +1]){ child++;}//大堆: >//小堆：<if(arr[child]> arr[parent]){//调整Swap(&arr[child],&arr[parent]); parent = child; child = parent *2+1;}else{break;}}}voidHPPop(HP* php){assert(!HPEmpty(php));// 0 php->size-1Swap(&php->arr[0],&php->arr[php->size -1]);--php->size;//向下调整AdjustDown(php->arr,0, php->size);}// 排升序，建⼤堆// 排降序，建⼩堆// O(N*logN)voidHeapSort(int* a,int n){// a数组直接建堆 O(N)for(int i =(n-1-1)/2; i >=0;--i){AdjustDown(a, n, i);}// O(N*logN)int end = n -1;while(end >0){Swap(&a[0],&a[end]);AdjustDown(a, end,0);--end;}}4.交换排序
交换排序基本思想：
所谓交换,就是根据序列中两个记录键值的⽐较结果来对换这两个记录在序列中的位置
交换排序的特点是:将键值较⼤的记录向序列的尾部移动,键值较⼩的记录向序列的前部移动
4.1冒泡排序(附动图)
冒泡排序是一种简单的交换排序方法,其基本思想是:从头扫描待排序的数据元素序列,依次比较相邻两个数据元素的关键字大小,如果逆序,则交换它们的位置,逐步将待排序列变成有序序列.
对于一个具有n个数据元素的序列,进行冒泡排序具体过程是:
①对待排序数据元素序列进行第一趟扫描,依次比较相邻两个数据元素的关键字大小,如果前面数据元素的关键字大于后面数据元素的关键字,就将它们交换,这样具有较大关键字的数据元素将不断后移,最后,具有最大关键字的数据元素移动到最后一个位置上;
②第二趟扫描仅需对前n-1个数据元素进行,重复以上操作,使具有次大关键字的数据元素移动到第n-1个位置;
③依此类推,直到某一趟扫描过程中没有发生数据元素的交换,则可结束冒泡排序.
因此,冒泡排序最多需进行n-1趟.
例如:对数据元素序列(35,66,2,15,6,81,6*,9)进行冒泡排序的过程.
冒泡排序是⼀种最基础的交换排序.之所以叫做冒泡排序,因为每⼀个元素都可以像⼩⽓泡⼀样,根据⾃⾝⼤⼩⼀点⼀点向数组的⼀侧移动.
voidSwap(int* x,int* y){int tmp =*x;*x =*y;*y = tmp;}//冒泡排序voidBubbleSort(int* arr,int n){for(size_t end = n; end >0;--end){int exchange =0;for(size_t i =1; i < end;++i){if(arr[i -1]> arr[i]){Swap(&arr[i -1],&arr[i]); exchange =1;}}if(exchange ==0)break;}}冒泡排序的特性总结:
时间复杂度：
最好情况(数组已有序): O (n)(仅需1轮遍历,无交换后直接终止);
最坏情况(数组逆序): O (n2)（需n-1轮遍历,每轮比较n-i次);
空间复杂度:O(1)(原地排序,仅用常数级临时变量);
4.2快速排序
快速排序的基本思想是:从待排数据元素序列中选取一个数据元素为基准,通过一趟扫描将待排序列分成两部分.其中一部分数据元素的关键字都小于或等于基准数据元素的关键字,而另一部分数据元素的关键字都大于或等于基准数据元素的关键字.对各部分不断划分,直到整个序列按关键字有序排列为止.
快速排序的具体过程如下:
①选取待排序列中的第一个数据元素为基准,将其复制到r[0]中,并令该位置为空;设置两个指针low和high,分别指向第一个数据元素和最后一个数据元素,即初始状态时r[low]为空.
②从后向前扫描,若r[high]的关键字大于或等于基准关键字,则 high向前移动一个位置,直到r[high]的关键字小于基准关键字时,将r[high]与r[low]交换.
③从前向后扫描,若r[low]的关键字小于或等于基准关键字,则low向后移动一个位置,直到r[low]的关键字大于基准关键字时,将r[low]与r[high]交换.
④重复步骤②和③,直至low=high时,令r[low]=r[0],以r[low]为基准将待排序列划分为前后两部分,第一次划分完成.
⑤按照以上方法,对各部分不断划分,直到各部分只有一个数据元素时,整个序列排序完成.
例如,对数据元素序列(35，66，2，15，6，81，6*，9)进行一趟快速排序的过程如图所示.
快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两⼦序列,左⼦序列中所有元素均⼩于基准值,右⼦序列中所有元素均⼤于基准值,然后最左右⼦序列重复该过程,直到所有元素都排列在相应位置上为⽌.
//快速排序voidQuickSort(int* a,int left,int right){if(left >= right){return;}//_QuickSort⽤于按照基准值将区间[left,right)中的元素进⾏划分int meet =_QuickSort(a, left, right);QuickSort(a, left, meet -1);QuickSort(a, meet +1, right);}//将区间中的元素进⾏划分的_QuickSort⽅法主要有以下⼏种实现⽅式：4.2.1hoare版本
算法思路 ：
1️⃣创建左右指针,确定基准值
2️⃣从右向左找出⽐基准值⼩的数据,从左向右找出⽐基准值⼤的数据,左右指针数据交换,进⼊下次循环
问题1:为什么跳出循环后right位置的值⼀定不⼤于key?
当left > right 时,即right⾛到left的左侧,⽽left扫描过的数据均不⼤于key,因此right此时指向的数据⼀定不⼤于key
问题2:为什么left 和 right指定的数据和key值相等时也要交换？
相等的值参与交换确实有⼀些额外消耗.实际还有各种复杂的场景,假设数组中的数据⼤量重复时,⽆法进⾏有效的分割排序.
//快速排序voidQuickSort(int* arr,int left,int right){if(left >= right){return;}//找基准值int keyi =_QuickSort(arr, left, right);//left keyi right//左序列[left,keyi-1] 右序列[keyi+1,right]QuickSort(arr, left, keyi -1);QuickSort(arr, keyi +1, right);}//hoare版本int_QuickSort1(int* arr,int left,int right){int keyi = left;++left;while(left <= right){//right：从右往左走，找比基准值要小的while(left <= right && arr[right]> arr[keyi]){ right--;}//left：从左往右走，找比基准值要大的while(left <= right && arr[left]< arr[keyi]){ left++;}//right left if(left <= right){Swap(&arr[left++],&arr[right--]);}}Swap(&arr[keyi],&arr[right]);return right;}//right:从右往左走,找比基准值要小的数据left:从左往右走,找比基准值要大的数据left<= right找到之后，让left和right交换当left>right,keyi和right数据交换,当基准值和left/right相等,也要交换hoare版本的快速排序特性总结:
时间复杂度:
平均:O (nlogn)（分治将问题拆分为logn层,每层处理 O (n) 元素）
最坏:O (n²)（若数组已有序,分治退化为 “单支递归”,如每次选左边界为基准的有序数组）
空间复杂度:O (logn)~O (n)（递归栈的深度,平均 logn,最坏 n）
4.2.2挖坑法(附动图)
思路：
创建左右指针.⾸先从右向左找出⽐基准⼩的数据,找到后⽴即放⼊左边坑中,当前位置变为新的"坑",然后从左向右找出⽐基准⼤的数据,找到后⽴即放⼊右边坑中,当前位置变为新的"坑",结束循环后将最开始存储的分界值放⼊当前的"坑"中,返回当前"坑"下标(即分界值下标)
int_QuickSort(int* a,int left,int right){int hole = left;int key = a[hole];while(left < right){while(left < right && a[right]>= key){--right;} a[hole]= a[right]; hole = right;while(left < right && a[left]<= key){++left;} a[hole]= a[left]; hole = left;} a[hole]= key;return hole;}挖坑法的快速排序特性总结:
相比 Hoare 版本,“挖坑法” 逻辑更直观(通过 “坑” 的转移替代双指针交换);
时间复杂度与快速排序一致:平均 O (nlogn),最坏O (n²);
空间复杂度:O (1)（原地分区）.
4.2.3lomuto前后指针(递归版本)
创建前后指针,从左往右找⽐基准值⼩的进⾏交换,使得⼩的都排在基准值的左边.
创建两个变量prev和cur;cur从左往右找比基准值要小的数据,prev和cur交换;cur探路,找比基准值要小的数据.
1️⃣cur找到了比基准值小的数据,++prev,prev和cur交换,cur++
2️⃣cur未找到比基准值小的数据,cur++
voidSwap(int* x,int* y){int tmp =*x;*x =*y;*y = tmp;}//lomuto前后指针法int_QuickSort(int* arr,int left,int right){int keyi = left;int prev = left, cur = prev +1;while(cur <= right){if(arr[cur]< arr[keyi]&&++prev != cur){Swap(&arr[prev],&arr[cur]);} cur++;}Swap(&arr[keyi],&arr[prev]);return prev;}快速排序特性总结：
时间复杂度:O(nlogn)
空间复杂度:O(logn)
4.2.4⾮递归版本的快速排序
⾮递归版本的快速排序需要借助数据结构:栈
//非递归版本的快速排序——栈voidQuicSortNoR(int* arr,int left,int right){ ST st;StackInit(&st);StackPush(&st, left);StackPush(&st, right);while(!StackEmpty(&st)){//取栈顶两次int end =StackTop(&st);StackPop(&st);int begin =StackTop(&st);StackPop(&st);//[begin,end]找基准值int keyi = begin;int prev = begin, cur = prev +1;while(cur <= end){if(arr[cur]< arr[keyi]&&++prev != cur){Swap(&arr[prev],&arr[cur]);} cur++;}Swap(&arr[keyi],&arr[prev]); keyi = prev;//begin keyi end//左序列：[begin,keyi-1] 右序列：[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);}}StackDestroy(&st);}//关于栈部分的代码前面文章内容里面有,这里就不展示了5.归并排序
“归并”是指将若干个有序表合并成一个新的有序表.归并排序(Mergeing Sort)就是利用“归并”技术来进行的排序,这里我们主要介绍二路归并排序.
归并排序的基本思想是:对于一个具有n 个数据元素的序列,将其中的每个数据元素看成长度为1的有序子表,然后对其进行两两归并,即第1个子表与第2个子表归并,第3个子表与第4个子表归并,依此类推,这样得到 n 2 \frac{n}{2} 2n个长度2的有序表(若n奇数,则最后一个有序表的长度为1);在此基础上再进行两两归并,得到 n 4 \frac{n}{4} 4n个长度为4的有序表(最后一个有序表的长度可能小于4),依此类推,直至得到一个长度为n的有序表为止.
例如,对数据元素序列(35，66，2，15，6，81，6*，9)进行归并排序的过程如图所示.
归并排序算法思想：
归并排序是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法的⼀个⾮常典型的应⽤.将已有序的⼦序列合并,得到完全有序的序列;即先使每个⼦序列有序,再使⼦序列段间有序.若将两个有序表合并成⼀个有序表,称为⼆路归并.归并排序核⼼步骤:
//归并排序void_MergeSort(int* arr,int left,int right,int* tmp){if(left >= right){return;}//[left,right]int mid =(left + right)/2;//根据mid划分左右两个序列：[left,mid] [mid+1,right]_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid +1, right, tmp);//合并两个有序的序列int begin1 = left, end1 = mid;int begin2 = mid +1, end2 = right;int index = begin1;//[begin1,end1] [begin2,end2]while(begin1 <= end1 && begin2 <= end2){if(arr[begin1]< arr[begin2]){ tmp[index++]= arr[begin1++];}else{ tmp[index++]= arr[begin2++];}}while(begin1 <= end1){ tmp[index++]= arr[begin1++];}while(begin2 <= end2){ tmp[index++]= arr[begin2++];}//tmp中有序的数据导入到原数组//[left,right]for(int i = left; i <= right; i++){ arr[i]= tmp[i];}}voidMergeSort(int* arr,int n){int* tmp =(int*)malloc(sizeof(int)* n);_MergeSort(arr,0, n -1, tmp);free(tmp); tmp =NULL;}归并排序特性总结：
时间复杂度:O(nlogn)(拆分区间的层数是O(logn),每层合并的总操作是O(n);
空间复杂度:O(n)(需要额外的临时数组tmp,大小与原数组一致);
6.计数排序(非比较排序)
计数排序⼜称为鸽巢原理,是对哈希直接定址法的变形应⽤.操作步骤:
1️⃣统计相同元素出现次数
2️⃣根据统计的结果将序列回收到原来的序列中
//计数排序voidCountSort(int* arr,int n){//找最大和最小值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];}}//max-min+1确定count数组的大小int range = max - min +1;int* count =(int*)malloc(sizeof(int)* range);if(count ==NULL){perror("malloc fail!");exit(1);}//初始化用callocmemset(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)
空间复杂度:O(range)
7.测试代码:排序性能对⽐
为了对比这些排序性能的高低,我们用时间去衡量.至于排序算法里面涉及到了栈相关的代码文件<stack.c><stack.h>可以翻看关于栈和队列写的文章去获取,以便能成功使用排序性能测试代码.
// 测试排序的性能对⽐voidTestOP(){srand(time(0));constint 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];}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);}sort.c代码
#include"sort.h"#include"Stack.h"//直接插入排序voidInsertSort(int* arr,int n){for(int i =0; i < n -1; i++){int end = i;int tmp = arr[end +1];while(end >=0){if(arr[end]> tmp){ arr[end +1]= arr[end]; end--;}else{break;}} arr[end +1]= tmp;}}//希尔排序voidShellSort(int* arr,int n){int gap = n;while(gap >1){ gap = gap /3+1;//3 2 1 //对每组进行直接插入排序for(int i =0; i < n - gap; i++){int end = i;int tmp = arr[end + gap];while(end >=0){if(arr[end]> tmp){ arr[end + gap]= arr[end]; end -= gap;}else{break;}} arr[end + gap]= tmp;}}}voidSwap(int* x,int* y){int tmp =*x;*x =*y;*y = tmp;}//冒泡排序voidBubbleSort(int* arr,int n){for(size_t end = n; end >0;--end){int exchange =0;for(size_t i =1; i < end;++i){if(arr[i -1]> arr[i]){Swap(&arr[i -1],&arr[i]); exchange =1;}}if(exchange ==0)break;}}//选择排序voidSelectSort(int* arr,int n){int begin =0, end = n -1;while(begin < end){int maxi = begin;int mini = begin;for(int i = begin +1; i <= end; i++){if(arr[i]< arr[mini]){ mini = i;}if(arr[i]> arr[maxi]){ maxi = i;}}//mini begin//maxi endif(maxi == begin){ maxi = mini;}Swap(&arr[mini],&arr[begin]);Swap(&arr[maxi],&arr[end]); begin++; end--;}}//向下调整算法voidAdjustDown(int* arr,int parent,int n){int child = parent *2+1;//左孩子while(child < n){//大堆：<//小堆：>if(child +1< n && arr[child]< arr[child +1]){ child++;}//大堆: >//小堆：<if(arr[child]> arr[parent]){//调整Swap(&arr[child],&arr[parent]); parent = child; child = parent *2+1;}else{break;}}}//排升序--- 建大堆//排降序--- 建小堆//堆排序voidHeapSort(int* arr,int n){//建堆——向下调整算法建堆for(int i =(n -1-1)/2; i >=0; i--){AdjustDown(arr, i, n);}//堆排序int end = n -1;while(end >0){Swap(&arr[0],&arr[end]);AdjustDown(arr,0, end); end--;}}//hoare版本int_QuickSort1(int* arr,int left,int right){int keyi = left;++left;while(left <= right){//right：从右往左走，找比基准值要小的while(left <= right && arr[right]> arr[keyi]){ right--;}//left：从左往右走，找比基准值要大的while(left <= right && arr[left]< arr[keyi]){ left++;}//right left if(left <= right){Swap(&arr[left++],&arr[right--]);}}Swap(&arr[keyi],&arr[right]);return right;}//lomuto前后指针法int_QuickSort(int* arr,int left,int right){int keyi = left;int prev = left, cur = prev +1;while(cur <= right){if(arr[cur]< arr[keyi]&&++prev != cur){Swap(&arr[prev],&arr[cur]);} cur++;}Swap(&arr[keyi],&arr[prev]);return prev;}//快速排序voidQuickSort(int* arr,int left,int right){if(left >= right){return;}//找基准值int keyi =_QuickSort(arr, left, right);//left keyi right//左序列[left,keyi-1] 右序列[keyi+1,right]QuickSort(arr, left, keyi -1);QuickSort(arr, keyi +1, right);}//非递归版本的快速排序——栈voidQuicSortNoR(int* arr,int left,int right){ ST st;StackInit(&st);StackPush(&st, left);StackPush(&st, right);while(!StackEmpty(&st)){//取栈顶两次int end =StackTop(&st);StackPop(&st);int begin =StackTop(&st);StackPop(&st);//[begin,end]找基准值int keyi = begin;int prev = begin, cur = prev +1;while(cur <= end){if(arr[cur]< arr[keyi]&&++prev != cur){Swap(&arr[prev],&arr[cur]);} cur++;}Swap(&arr[keyi],&arr[prev]); keyi = prev;//begin keyi end//左序列：[begin,keyi-1] 右序列：[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);}}StackDestroy(&st);}//归并排序void_MergeSort(int* arr,int left,int right,int* tmp){if(left >= right){return;}//[left,right]int mid =(left + right)/2;//根据mid划分左右两个序列：[left,mid] [mid+1,right]_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid +1, right, tmp);//合并两个有序的序列int begin1 = left, end1 = mid;int begin2 = mid +1, end2 = right;int index = begin1;//[begin1,end1] [begin2,end2]while(begin1 <= end1 && begin2 <= end2){if(arr[begin1]< arr[begin2]){ tmp[index++]= arr[begin1++];}else{ tmp[index++]= arr[begin2++];}}while(begin1 <= end1){ tmp[index++]= arr[begin1++];}while(begin2 <= end2){ tmp[index++]= arr[begin2++];}//tmp中有序的数据导入到原数组//[left,right]for(int i = left; i <= right; i++){ arr[i]= tmp[i];}}voidMergeSort(int* arr,int n){int* tmp =(int*)malloc(sizeof(int)* n);_MergeSort(arr,0, n -1, tmp);free(tmp); tmp =NULL;}//计数排序voidCountSort(int* arr,int n){//找最大和最小值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];}}//max-min+1确定count数组的大小int range = max - min +1;int* count =(int*)malloc(sizeof(int)* range);if(count ==NULL){perror("malloc fail!");exit(1);}//初始化用callocmemset(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;}}}sort.h代码
#pragmaonce#include<stdio.h>#include<stdlib.h>#include<string.h>#include<time.h>//voidInsertSort(int* arr,int n);//voidShellSort(int* arr,int n);//voidBubbleSort(int* arr,int n);//voidQuickSort(int* arr,int left,int right);voidQuicSortNoR(int* arr,int left,int right);//voidSelectSort(int* arr,int n);//voidHeapSort(int* arr,int n);//voidMergeSort(int* arr,int n);//voidCountSort(int* arr,int n);test.c代码
#include"sort.h"voidarrprint(int* arr,int n){for(int i =0; i < n; i++){printf("%d ", arr[i]);}printf("\n");}voidtest01(){//int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int a[]={100,101,109,105,101,105};int n =sizeof(a)/sizeof(a[0]);printf("排序之前：");arrprint(a, n);//InserSort(a, n);//ShellSort(a, n);//SelectSort(a, n);//QuickSort(a, 0, n - 1);//QuicSortNoR(a, 0, n - 1);//MergeSort(a, n);CountSort(a, n);printf("排序之后：");arrprint(a, n);}// 测试排序的性能对⽐voidTestOP(){srand(time(0));constint 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];}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);}intmain(){//test01();TestOP();return0;}从测试的结果来看:我们就能直观的看出每个排序算法的性能高低.
8.排序算法复杂度及稳定性分析
稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,⽽在排序后的序列中,r[i]仍在r[j]之前则称这种排序算法是稳定的;否则称为不稳定的.
敬请期待下一篇文章内容:数据结构之快速排序和归并排序的深入优化
