【C语言】排序算法——快速排序详解（含多种变式）！！！
【C语言】排序算法——快速排序详解（含多种变式）！！！
前言
在上一期，我们学习了希尔排序以及插入排序，这些排序的算法都很高
那么，还有什么高效的排序算法呢？
今天给大家带来的是被加入C语言库里的排序算法——快速排序
（本期讲快速排序由初阶到高阶，还有一些拓展，方便大家理解）
一 、快速排序（初阶)
1. 视频演示
首先给大家看一段视频，让大家先看看快速排序是怎么运行的
（该视频仅仅是一次快速排序）
快速排序视频演示
2. 算法思想
（该视频仅仅是一次快速排序）
快速排序有一个key值，叫基准元素，可以理解为就是要排序数组的第一个数字
视频里可以看到，在第一次快速排序结束后，这个key值位置发生改变，其他元素位置也发生一定改变
最后在key的左边都是小于key的数，在key的右边都是大于key的数
这就是一次快速排序，此时key的顺序就被排好了，后续也不需要动
然后，将整个数组以key分成两个左右两个区间，并在这两个区间循环刚刚的步骤
直到区间不可再分（区间只剩一个元素），此时排序结束
一句话总结，快速排序就是不断将比 key 小的数放左边，把比 key 大的数放右边
最后完成排序
3. 实现思路
大体的排序逻辑我们讲完了，那现在该怎么实现呢？
（1）定key值
- 第一步：定key值
快速排序有一个key值，叫基准元素，现在可以理解为就是第一个数字（后续还会再改进）
后续的排序就是围绕这个基准元素key来进行的
（2）大小交换
- 第二步：大小交换
我们可以发现，视频中有两个小人，一个从左边往右走，一个从右往左走
先右小人一直向左走，直到遇到比key大的数停下
再左小人一直向右走，直到遇到比key小的数停下
当两小人都停下后，两小人所对应的值就互相交换，大的数换到右边，小的数换到左边
（3）循环
- 第三步：循环
两小人继续一个左走，一个右走，满足条件时继续交换，然后重复
直到两小人相遇循环停止
（4）交换key
- 第四步：交换key
此时将key与两小人相遇点的值进行交换
此时在key的左边都是小于key的数，在key的右边都是大于key的数
此时key就已经排好序，后续也不需要再动，第一轮快速排序结束
（5）分割区间
- 第五步：分割区间
现在，key就已经排好序，后续也不需要再动
此时将key左右的区间分割开来，分成左右两个区间
然后分别对这两个区间重复第一轮的排序：
定key值、大小交换、循环、交换key、分割区间
（6）结束
- 第六步：结束
当每个区间分割成只剩下一个元素时，自然也不需要继续循环，就可以跳出循环
当所有的区间都只剩下一个元素时，都跳出循环时，排序也就完成了
4. 实现代码
刚刚给大家详细讲解了一下快速排序的实现思路
现在，我们开始实现代码
定义两个指针，也就是两个小人，排序完一次后开始递归key的左右区间
直到所有区间都跳出循环，排序结束
代码演示：（内有注释）
voidQuickSort1(int* a,int left,int right){if(left >= right)//判断是否继续，当区间只有一个数时跳出循环{return;}int key = left;//确定key的值，为第一个元素int L = left;int R = right;//先将左右的下标记录下来，以免后面丢失while(left < right)//当左右小人相遇时就停止循环{while(left < right && a[right]>= a[key])//右小人向左走，直到找到比key小的值{ right--;}while(left < right && a[left]<= a[key])//左小人向右走，直到找到比key大的值{ left++;}Swap(&a[left],&a[right]);//交换大的值和小的值}Swap(&a[right],&a[key]);//最后交换key和相遇点对应的值 key = right;//key的下标也要改变QuickSort1(a, L, key -1);//递归key的左区间QuickSort1(a, key +1, R);//递归key的右区间}二 、快速排序（中阶)
1. 存在的问题
在刚刚快速排序的初阶代码中
我们的key值是固定的，始终都是数组的第一项
但这样也会出现一些小问题
若这个数组是完全有序的，会出现什么情况呢？
首先，右小人先向左走，因为数组是有序的，找不到比第一个数key小的值
所以会一直走直到找到key，且左右小人相遇 ( 左小人起始位置为key)
然后分割区间，key单独一个区间，右边所有数一个区间，然后循环右区间
最后当排序结束时，发现每一次循环都只排好一个数，时间复杂度为O（N ^ 2）
所以，当数组的顺序有序或几乎有序时，key值就容易取到数组的极值，算法就很慢
2. 优化（三数取中）
那怎么来优化呢？
这里我们可以用三数取中的方法来解决取到极值
意思就是取数组的开头、中间、结尾三个数，数的大小在中间的就定为key
可以一定程度上避免取到极值点
代码演示：（内有注释）
//三数取中，返回三个数的中间值intFindKey(int* a,int left,int right)//形参为数组以及左右两下标{int mid =(left + right)/2;//中间数的下标if(a[left]> a[right]){if(a[right]> a[mid]){return right;}elseif(a[mid]> a[left]){return left;}else{return mid;}}else{if(a[left]> a[mid]){return left;}elseif(a[mid]> a[right]){return right;}else{return mid;}}}3. 实现代码（中阶）
我们可以封装成一个函数来使用：
代码演示：（内有注释）
voidQuickSort1(int* a,int left,int right){if(left >= right)//判断是否继续，当区间只有一个数时跳出循环{return;}int L = left;int R = right;//先将左右的下标记录下来，以免后面丢失int key =FindKey(a, left, right);Swap(&a[key],&a[left]); key = left;while(left < right)//当左右小人相遇时就停止循环{while(left < right && a[right]>= a[key])//右小人向左走，直到找到比key小的值{ right--;}while(left < right && a[left]<= a[key])//左小人向右走，直到找到比key大的值{ left++;}Swap(&a[left],&a[right]);//交换大的值和小的值}Swap(&a[right],&a[key]);//最后交换key和相遇点对应的值 key = right;//key的下标也要改变QuickSort1(a, L, key -1);//递归key的左区间QuickSort1(a, key +1, R);//递归key的右区间}三 、快速排序（高阶)
1. 仍存在的问题
由于我们的快速排序是由递归实现的，每递归一次就多一半的区间，最后的区间数是 2^n ( n为递归次数 ）
而在第倒数1、2个递归时，区间内只有几个数，这时候用之前的办法就效率不高，且还会多两倍的区间
所以，我们可以当区间内个数少于一定是时，采用其他排序，这样就可以减少大量的递归，提高效率
2. 优化（小区间优化）
当区间个数小于10时，就采用推排序，可以有效的提高效率
3. 实现代码（高阶）
（包含堆排）
（1）三数取中函数
代码演示：（内有注释）
//三数取中，返回三个数的中间值intFindKey(int* a,int left,int right){int mid =(left + right)/2;//中间数的下标if(a[left]> a[right]){if(a[right]> a[mid]){return right;}elseif(a[mid]> a[left]){return left;}else{return mid;}}else{if(a[left]> a[mid]){return left;}elseif(a[mid]> a[right]){return right;}else{return mid;}}}（2）主要的快速排序代码
代码演示：（内有注释）
// 快速排序递归实现// 快速排序hoare版本intPartSort1(int* a,int left,int right){int key =FindKey(a, left, right);//找到中间下标并给keySwap(&a[key],&a[left]); key = left;//将key位置换到首项while(left < right)//当左右小人相遇时就停止循环{while(left < right && a[right]>= a[key])//右小人向左走，直到找到比key小的值{ right--;}while(left < right && a[left]<= a[key])//左小人向右走，直到找到比key大的值{ left++;}Swap(&a[left],&a[right]);//交换大的值和小的值}Swap(&a[right],&a[key]);//最后交换key和相遇点对应的值return right;//返回最后key的下标，方便分割}（3）堆排序
代码演示：（内有注释）
// 插入排序voidInsertSort(int* a,int n){// [0, n-1]for(int i =0; i < n -1; i++){// [0, n-2]是最后一组// [0,end]有序 end+1位置的值插入[0,end]，保持有序int end = i;int tmp = a[end +1];while(end >=0){if(tmp < a[end]){ a[end +1]= a[end];--end;}else{break;}} a[end +1]= tmp;}}// 将交换的元素向下调整voidAdJustDown(int* a,int parent,int size){// 先假设左孩子小int child =2* parent +1;while(child <= size -1){if(child +1<= size -1&& a[child +1]> a[child]){ child++;}if(a[child]> a[parent]){Swap(&a[child],&a[parent]); parent = child; child =2* parent +1;}else{break;}}}//堆排序voidHeapSort(int* a,int sz){int i;for(i =(sz -1-1)/2; i >=0; i--){AdJustDown(a, i, sz);}for(i = sz -1; i >0; i--){Swap(&a[0],&a[i]);AdJustDown(a,0, i);}}（4）快速排序的框架
代码演示：（内有注释）
voidQuickSort1(int* a,int left,int right){if(left >= right)//判断是否继续，当区间只有一个数时跳出循环{return;}int g = right - left +1;if(g <10){HeapSort(a + left, g);//堆排序}else{int key =PartSort1(a, left, right);//接收返回值QuickSort1(a, left, key -1);//递归key的左区间QuickSort1(a, key +1, right);//递归key的右区间}}四、快速排序（非递归)
1. 问题
在我们进行递归的快速排序时，若数据量过大，就会递归很多次，可能会出现栈溢出
为了避免出现这种情况，我们可以采用非递归的方式解决
2.实现思路
我们可以使用一个栈来实现
将区间的左、右范围分别存在栈中，当取出一个区间后，就存下这个区间的两个分割区间
（前提是区间存在）
当栈为空且不能再存入时，排序就好了
3.实现代码
注意：由于小编在之前的博客中详解了栈的实现，为了避免重复，小编在这里没有讲解栈的实现代码
若有感兴趣的可以去看看
链接：【数据结构】栈——超详解！！！（包含栈的实现）
（1）栈的实现（Stack.h）
用于存放用来放函数的声明和一些库函数的头文件
#pragmaonce#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>#include<sperror.h>//重定义，方便修改类型typedefint STDataType;//定义栈typedefstructStack{ STDataType* a;//数组指针int size;//总元素int capacity;//容量 }Stack;// 初始化栈 voidStackInit(Stack* ps);// 入栈 voidStackPush(Stack* ps, STDataType data);// 出栈 voidStackPop(Stack* ps);// 获取栈顶元素 STDataType StackTop(Stack* ps);// 获取栈中有效元素个数 intStackSize(Stack* ps);// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 intStackEmpty(Stack* ps);// 销毁栈voidStackDestroy(Stack* ps);（2）栈的实现（Stack.c）
用于用来放函数的定义(栈的主体)
#include"Stack.h"// 初始化栈 voidStackInit(Stack* ps){//断言空指针assert(ps); ps->a =NULL; ps->capacity =0; ps->size =0;//全部初始化置 0 / NULL}// 入栈 voidStackPush(Stack* ps, STDataType data){assert(ps);//断言空指针if(ps->size == ps->capacity)//当size=capacity时就表示空间不足，此时需要增容，故进入if语句{//先设置新变量，增容后再赋值int newcapacity = ps->capacity ==0?4:2* ps->capacity;//设置一个三目操作符判断原空间是否为 0//当原空间为0时给空间开辟 4 字节；当原空间不为0时给空间增容 2倍 STDataType* tmp =(STDataType*)realloc(ps->a, newcapacity *sizeof(STDataType));//由于是在原空间的基础上给空间增容，故我们这里使用 realloc函数 增容//增容大小为上面的 newcapacity *（类型大小）if(tmp ==NULL)//加一个 if语句 防止增容失败{perror("realloc");return;}//没有问题后就赋值 ps->a = tmp; ps->capacity = newcapacity;} ps->a[ps->size]= data; ps->size++;}// 出栈 voidStackPop(Stack* ps){assert(ps && ps->size >0);//断言空指针//断言顺序表不能为空 ps->size--;//将元素个数进行 -1 就行//这样也不会影响到后面的 增、删、查、改}// 获取栈顶元素 STDataType StackTop(Stack* ps){assert(ps && ps->size >0);//断言空指针//断言顺序表不能为空return ps->a[ps->size -1];}// 获取栈中有效元素个数 intStackSize(Stack* ps){assert(ps);//断言空指针return ps->size;}// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 intStackEmpty(Stack* ps){assert(ps);//断言空指针return ps->size ==0;}// 销毁栈 voidStackDestroy(Stack* ps){assert(ps);//断言空指针free(ps->a);//释放内存 ps->a =NULL; ps->capacity =0; ps->size =0;//全部初始化置 0 / NULL}（3）快速排序主体
（下面重复的函数上面都有）
代码演示：（内有注释）
// 快速排序 非递归实现voidQuickSortNonR(int* a,int left,int right){//定义 Stack S;StackInit(&S);//首次添加数据StackPush(&S, right);StackPush(&S, left);//当栈不为空时循环while(!StackEmpty(&S)){int L =StackTop(&S);StackPop(&S);int R =StackTop(&S);StackPop(&S);//取出值并从栈删除if(L >= R){return;}//小区间优化int g = R - L +1;if(g <10){//堆排序HeapSort(a + L, g);}else{int key =PartSort1(a, L, R);//没越界就插入新数据if(R - key -1>1){StackPush(&S, R);StackPush(&S, key +1);}if(key -1- L >1){StackPush(&S, key -1);StackPush(&S, L);}}}//最后销毁StackDestroy(&S);}结语
OK，本期的排序算法详解到这里就结束了
若内容对大家有所帮助,可以收藏慢慢看,感谢大家支持
本文有若有不足之处，希望各位兄弟们能给出宝贵的意见。谢谢大家！！！
新人，本期制作不易希望各位兄弟们能动动小手，三连走一走！！！
支持一下（三连必回QwQ）
