快速排序（递归）——C语言实现

爆肝一万字，全网最详细的快速排序，你想到的，你想不到的这里都有。
🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥

文章目录

⚽一、快速排序

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

🏀二、快速排序之“挖坑法”

🥪2.1 挖坑法思路

⛳ 单趟排序：单趟排序的目的就是使当前的key值放到它最终的位置，左边全是比它小的数，右边全是比它大的数。我们一般选取第一个值或者最后一个值做key，pivot初始值为初始的key值的位置，这里也就是第一个位置。当pivot在begin的位置时，end从右往左开始找比key小的值，找到后将它放到pivot的地方，也就是填坑，填完之后自己形成新的坑位；pivot在end的位置时，begin从左往右开始找比key大的数，找到之后进行填坑，直到begin和end相遇时，最后将key放至相遇点即可。

🍟2.2 挖坑法图解

第一步：定义begin，end，key，pivot这四个变量。这里选第一个值最为key，那么第一个值自然就是pivot。

第二步：将key值拿走，第一个值成为pivot。

第三步：这时候pivot在begin位置，那么end就开始从右至左找比key小的值，找到后放入pivot。所以将2放到pivot的位置，end成为新的pivot。

第四步：这时候pivot在end位置，那么begin开始从左至右找比key大的值，找到后放入pivot。所以将8放到pivot的位置，begin成为新的pivot。

第五步：end继续找小，找到4放到pivot，end成为新的pivot。

第六步：begin继续找大，这里与end汇合了，停止循环，把key放到相遇位置即可。

🥯2.3 挖坑法动图展示

🧀2.4 单趟排序的代码

voidQuickSort(int* arr,int n){int begin =0;int end = n-1;int key = arr[begin];int pivot = begin;while(begin < end){//pivot在begin那边，则end这边找比key小while(begin < end&&arr[end]>= key){
            end--;}//循环结束则为找到该小值,将之赋值给arr[pivot]
        arr[pivot]= arr[end];//自己形成新的坑位
        pivot = end;//piovt在end那边，则begin这边找比key大while(begin < end&&arr[begin]<= key){
            begin++;}//循环结束则为找到该大值,将之赋值给arr[pivot]
        arr[pivot]= arr[begin];//自己形成新的坑位
        pivot = begin;}//循环结束代表begin和end相遇，并且相遇在坑（pivot）
    pivot = begin;//这里给begin和end都可以//将key放到pivot
    arr[pivot]= key;}

🌭2.5 挖坑法总体代码实现

单趟排完后，已经有一个值被放到了正确的位置，以该值做分割，此时区间被分为左右两个子区间，然后对左右两个子区间进行递归即可。

#include<stdio.h>voidPrint(int* arr,int n){for(int i =0; i < n; i++){printf("%d ", arr[i]);}}voidQuickSort(int* arr,int left,int right){//当区间被分到只有1个元素时，则返回//=代表只有一个元素，>代表没有右区间，为什么会出现大于可以看下面递归图if(left >= right){return;}int begin = left;int end = right;int key = arr[begin];int pivot = begin;while(begin < end){//pivot在begin那边，则end这边找比key小while(begin < end&&arr[end]>= key){
            end--;}//循环结束则为找到该小值,将之赋值给arr[pivot]
        arr[pivot]= arr[end];//自己形成新的坑位
        pivot = end;//piovt在end那边，则begin这边找比key大while(begin < end&&arr[begin]<= key){
            begin++;}//循环结束则为找到该大值,将之赋值给arr[pivot]
        arr[pivot]= arr[begin];//自己形成新的坑位
        pivot = begin;}//循环结束代表begin和end相遇，并且相遇在坑（pivot）
    pivot = begin;//这里给begin和end都可以//将key放到pivot
    arr[pivot]= key;//将区间分为[left,pivot-1] pivot [pivot+1,right]//采用分治递归，左边有序了，右边有序了，则整体有序QuickSort(arr, left, pivot -1);QuickSort(arr, pivot +1, right);}voidtest01(){int arr1[]={5,8,1,4,9,6,2};int n =sizeof(arr1)/sizeof(arr1[0]);QuickSort(arr1,0, n -1);Print(arr1, n);}intmain(){test01();return0;}

🍖2.6 递归展开图（用于理解）

🏐三、时间复杂度分析

✈️3.1 计算时间复杂度

我们先计算单趟排序的时间复杂度，很简单，单趟排序就是begin和end两个指针往中间一起走知道汇合，将数组遍历了一遍，所以单趟排序的时间复杂度为O(N)。
递归的时间复杂度，我们假设每次取到的数都是中间数，也就是接近二分，看下图:
把它看出一颗完全二叉树，每一层都是N个数，总共有logN层，所以总体的时间复杂度为O(N*logN)。但是这是理想情况，那么最坏情况又是什么时候呢？没错，就是序列有序时最坏。看下图：

每次只排好一个上数，那么我们递归的深度就是N，每趟时间复杂度O(N)，那么N趟下来就是O(N^2)。

🚀3.2 优化最坏时间复杂度（三数取中）

由上面的时间复杂度分析可知，当序列有序时，时间复杂度为O（N^2）。这是因为我们选的key值总是最大或者最小，所以我们只要保证所选的值不是最大或者最小就能达到优化的效果。这里我们采取三数取中。

🏕三数取中基本思想：取序列中的左右中三个数选出中间值最为key值进行排序。

三数取中的代码为：

intGetMinIndex(int* arr,int left,int right){int mid =(left + right)>>1;if(arr[left]< arr[mid]){if(arr[mid]< arr[right]){return mid;}if(arr[left]< arr[right]&& arr[right]< arr[mid]){return right;}return left;}else//arr[left] >= arr[mid]{if(arr[left]< arr[right]){return left;}if(arr[mid]<arr[right]&& arr[right]< arr[left]){return right;}return mid;}}

将之运用到快速排序代码：

voidSwap(int* p1,int*p2){int tmp =*p1;*p1 =*p2;*p2 = tmp;}voidQuickSort(int* arr,int left,int right){//当区间被分到只有1个元素时，则返回if(left >= right){return;}int index =GetMinIndex(arr, left, right);//因为我们下面的逻辑都是把第一个数作为key，//为了避免改动代码，这里我们直接交换就可以Swap(&arr[left],&arr[index]);int begin = left;int end = right;int key = arr[begin];int pivot = begin;while(begin < end){//pivot在begin那边，则end这边找比key小while(begin < end&&arr[end]>= key){
            end--;}//循环结束则为找到该小值,将之赋值给arr[pivot]
        arr[pivot]= arr[end];//自己形成新的坑位
        pivot = end;//piovt在end那边，则begin这边找比key大while(begin < end&&arr[begin]<= key){
            begin++;}//循环结束则为找到该大值,将之赋值给arr[pivot]
        arr[pivot]= arr[begin];//自己形成新的坑位
        pivot = begin;}//循环结束代表begin和end相遇，并且相遇在坑（pivot）
    pivot = begin;//这里给begin和end都可以//将key放到pivot
    arr[pivot]= key;//将区间分为[left,pivot-1] pivot [pivot+1,right]//采用分治递归，左边有序了，右边有序了，则整体有序QuickSort(arr, left, pivot -1);QuickSort(arr, pivot +1, right);}

采取三数取中后，快排不会出现最快情况，时间复杂度就是O(N*logN)。

⚾四、递归调用的内存消耗

🐧4.1 内存消耗

这里我们先解释一下什么是函数栈帧。

🌴函数栈帧：C语言中，每个栈帧对应着一个未运行完的函数，栈帧中保存着该函数的函数地址和局部变量。

由此可见，每一次递归调用时，都会在内存的栈区上存一个函数栈帧，当递归的深度过深时，就可能导致栈溢出。

🐤4.2 优化内存消耗（小区间优化）

为了减少递归调用的内存消耗，这里我们做一个小小的优化——小区间优化。看下图：
我我们假设有100万个数需要排序，那我们就得调用100万次，栈上就需要存储100万个函数栈帧，显然这不是我们想要看到的结果。我们需要将之优化一下。最后由上图可以看到，最后三层的调用就占了87.5万次，所以我们只需要将最后三层的调用消除，就可以达到优化的效果。
如何优化：倒数第三层时，子区间差不多被分到了不到10个数，数据量极小，所以我们只需要采用直接插入排序就可以了。我们需要改动的代码就只有最后递归时候，需要加上判断条件。

//将区间分为[left,pivot-1] pivot [pivot+1,right]if(pivot-1-left>13){QuickSort(arr, left, pivot -1);}else{InsertSort(arr+left, pivot-1-left+1);}if(right-(pivot+1)>13){QuickSort(arr,pivot+1,right);}else{InsertSort(arr+pivot+1, right-(pivot+1)+1);}

InsertSort为插入排序，这里的代码就不再赘述了，直接使用。
详情可点击——>>插入排序详解

🏀五、加上三数取中和小区间优化后的完整代码

#include<stdio.h>//打印函数voidPrint(int* arr,int n){for(int i =0; i < n; i++){printf("%d ", arr[i]);}}//交换函数voidSwap(int* p1,int*p2){int tmp =*p1;*p1 =*p2;*p2 = tmp;}//直接插入排序voidInsertSort(int* arr,int sz){for(int i =0; i < sz -1; i++)//注意这里i相当于就等end，i必须是小于sz-1{//此for循环是要排序的趟数int end = i;int tmp = arr[end +1];//此while循环是一趟下来要比较的次数while(end >=0)//只要end没出界就继续比较{if(tmp < arr[end]){//在比较的过程中只要tmp值比arr[end]小，就向后移动arr[end]
                arr[end +1]= arr[end--];//end--;}else{//一旦出现相等或者比arr[end]大,就将tmp插入到arr[end+1]处//这里break掉是因为，如果循环结束，说明要插入的值比所以的值都要小，//要插入到头部，所有到while后面一并处理break;}}
        arr[end +1]= tmp;}}//三数取中intGetMinIndex(int* arr,int left,int right){int mid =(left + right)>>1;if(arr[left]< arr[mid]){if(arr[mid]< arr[right]){return mid;}if(arr[left]< arr[right]&& arr[right]< arr[mid]){return right;}return left;}else//arr[left] >= arr[mid]{if(arr[left]< arr[right]){return left;}if(arr[mid]< arr[right]&& arr[right]< arr[left]){return right;}return mid;}}//快速排序挖坑法voidQuickSort(int* arr,int left,int right){//当区间被分到只有1个元素时，则返回if(left >= right){return;}int index =GetMinIndex(arr, left, right);//因为我们下面的逻辑都是把第一个数作为key，//为了避免改动代码，这里我们直接交换就可以Swap(&arr[left],&arr[index]);int begin = left;int end = right;int key = arr[begin];int pivot = begin;while(begin < end){//pivot在begin那边，则end这边找比key小while(begin < end&&arr[end]>= key){
            end--;}//循环结束则为找到该小值,将之赋值给arr[pivot]
        arr[pivot]= arr[end];//自己形成新的坑位
        pivot = end;//piovt在end那边，则begin这边找比key大while(begin < end&&arr[begin]<= key){
            begin++;}//循环结束则为找到该大值,将之赋值给arr[pivot]
        arr[pivot]= arr[begin];//自己形成新的坑位
        pivot = begin;}//循环结束代表begin和end相遇，并且相遇在坑（pivot）
    pivot = begin;//这里给begin和end都可以//将key放到pivot
    arr[pivot]= key;//将区间分为[left,pivot-1] pivot [pivot+1,right]//采用分治递归，左边有序了，右边有序了，则整体有序//小区间优化if(pivot -1- left >10){QuickSort(arr, left, pivot -1);}else{InsertSort(arr + left, pivot -1- left +1);}if(right -(pivot +1)>10){QuickSort(arr, pivot +1, right);}else{InsertSort(arr + pivot +1, right -(pivot +1)+1);}}voidtest01(){int arr1[]={5,8,1,4,9,6,2};int n =sizeof(arr1)/sizeof(arr1[0]);QuickSort(arr1,0, n -1);Print(arr1, n);}intmain(){test01();return0;}

⚽六、快速排序之“左右指针法”

理解了前面的挖坑法，左右指针法将不难理解。

🎺6.1 左右指针法思路

🌲定义begin和end两个指针，end从右向左找比key值小的，找到停下；begin从左向右找比key值大的，找到停下；然后交换这两个值，一直循环下去，直到相遇。

🎸6.2 左右指针法图解

还是拿arr=[5,8,1,4,9,2,6]为例
第一步：定义号begin，end，和key，我们取第一个值为key。

第二步：end从右向左找比key值小的，找到8停下；begin从左向右找比key值大的，找到2停下。特别注意：选左边作为key，要保证右边的end先动。

第三步：交换8和2；

第四步：end继续从右向左找比key值小的，找到4停下；begin从左向右找比key值大的，没找到，但是在4的位置于end相遇了，停下。

第五步：相遇位置的值一定小于key，交换key和相遇位置的值，也就是5和4。单趟排序完毕。

🎻6.3 动图演示

🎷6.4 左右指针法代码

//快速排序左右指针法voidQuickSort(int*arr,int left,int right){if(left >= right){return;}//三数取中int index =GetMinIndex(arr, left, right);Swap(&arr[left],&arr[index]);int begin = left;int end = right;int key = arr[begin];while(begin < end){//end找小while(begin < end && arr[end]>= key){
            end--;}//begin找大while(begin < end && arr[begin]<= key){
            begin++;}Swap(&arr[begin],&arr[end]);}Swap(&arr[begin],&key);//将区间分为[left,begin-1] begin [begin+1,right]//小区间优化if(begin -1- left >10){QuickSort1(arr, left, begin -1);}else{InsertSort(arr + left, begin -1- left +1);}if(right -(begin +1)>10){QuickSort1(arr, begin +1, right);}else{InsertSort(arr + begin +1, right -(begin +1)+1);}}

🥁6.5 问题分析

//end找小while(begin < end && arr[end]>= key){
            end--;}

对于上面这段代码，有些人会有个疑问，为什么要在判断条件上加上begin<end。如果这个地方不加这个条件，那么在极端条件下，也就是顺序的情况下，end永远不会小于key，while循环不会在正常范围内停下来，就会一直减减直到数组越界。当然加了三数取中后，是不会出现这种情况的，但不是每个时候都有三数取中。

那如果将arr[end]>=key改成arr[end]>key能解决问题吗？看似解决了，实则衍生出了新的问题。看下图，可能会造成死循环。

🎱七、快速排序之“前后指针法”

🚗7.1 前后指针法思路

🎋定义一前一后两个指针，prev和cur，以及一个key值，key值取第一个值。prev指向第一个值，cur指向第二个值。cur从左向右找比key小的值，找到停下，然后prev++，然后交换arr[cur]和arr[prev]，循环下去直到cur将数组遍历完。

🚙7.2 图解

第一步：将第一个值作为key值，定义prev和cur。

第二步：cur向右找小，找到1停下，prev++到8的位置，交换1和8。

第三步：cur继续向右找小，找到4停下，prev++到8的位置，交换8和4。

第四步：cur继续向右找小，找到2停下，prev++到8的位置，交换8和2。

第五步：cur继续向右找小，越界停止，交换key和prev位置的值，也就是5和2。

🚕7.3 动图演示

🚛7.4 前后指针法代码

//前后指针法voidQuickSort3(int*arr,int left,int right){if(left >= right){return;}//三数取中int index =GetMinIndex(arr, left, right);Swap(&arr[left],&arr[index]);int prev = left;int cur = left +1;int key = arr[left];while(cur <= right){//cur找小while(arr[cur]< key &&++prev != cur){Swap(&arr[prev],&arr[cur]);}
        cur++;}Swap(&arr[prev],&key);//将区间分为[left,prev-1] prev [prev+1,right]//小区间优化if(prev -1- left >10){QuickSort1(arr, left, prev -1);}else{InsertSort(arr + left, prev -1- left +1);}if(right -(prev +1)>10){QuickSort1(arr, prev +1, right);}else{InsertSort(arr + prev +1, right -(prev +1)+1);}}

🚜7.5 问题分析

//cur找小while(arr[cur]< key &&++prev != cur){Swap(&arr[prev],&arr[cur]);}

在上面的代码中，为什么要加上++prev != cur？

这是为了避免prev和cur走到一个位置上，交换同样的数，没有必要。