一文带你学透快排（快速排序C语言版）
一、什么是快速排序？
快速排序(QuickSort)采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素pivot，利用pivot将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，直到将无序序列排列成有序序列。 ——————百度百科
快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
1、首先设定一个分界值，通过该分界值将数组分成左右两部分。
2、将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。
3、然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4、重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
实际快速排序方式这种方式就是先选取一个基准值，在使用两个左右指针，将小于基准值的数据甩到左边，将大于基准值的数据甩到右边，再将基准值与指针相遇处交换位置。这样一趟排序就完成了，接下来只要将基准值左边与右边重复同样的工作，最后整个数组就会有序起来。
二、快排的实现
1）三数取中：
我们在选取基准值进行预排序时，想象一下，如果基准值在中间是最好的结果，但是不能保证每次所取的基准值都是正好的，如果每次选取的基准值在最左边或者最右边的时候，每次都递归都会出现“头重脚轻”的情况，这样时间复杂度就变得高了。
有什么好方法能改善这样状况呢？当然有，有种算法叫三数取中，可以尽量将靠近中间的值取出来，实现起来也很简单，将数组的最左下标与数组的最右下标相加除与2，直接索引中间值在与左和右下标进行比较，返回中间值就行。
代码实现如下：
int GetMid(int *a, int left , int right) //三数取中
{
assert(a);
int mid = (left + right) / 2;
if(a[left] < a[mid])
{
if(a[mid] < a[right])
{
return mid;
}
else if(a[left] < a[right])
{
return right;
}
else
{
return right;
}
}
else
{
if(a[mid] > a[right])
{
return mid;
}
else if(a[right] > a[left])
{
return left;
}
else
{
return right;
}
}
}2）霍尔法快排实现：
快排首先是被霍尔大佬提出来的，实现的方案有些复杂，首先需要两个指针（left, right）左指针指向数组首元素下标，右指针指向数组末元素下标，以数组首元素为基准值，以基准值（pivot）为界限，左右指针把小于pivot的数据甩到左边，大于pivot的数据甩到右边。
右指针先开始向左寻找比pivot小的，找到与左指针交换，然后左指针向右寻找比pivot大的值与右指针交换，一直重复这个过程，直到两指针相遇，最后在交换基准值与指针相遇位置的值，这一趟就结束了。随后在对数组基准值的左边和右边进重样操作。
过程图如下：
代码实现：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<assert.h>
void Swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
return;
}
int GetMid(int *a, int left , int right) //三数取中
{
assert(a);
int mid = (left + right) / 2;
if(a[left] < a[mid])
{
if(a[mid] < a[right])
{
return mid;
}
else if(a[left] < a[right])
{
return right;
}
else
{
return right;
}
}
else
{
if(a[mid] > a[right])
{
return mid;
}
else if(a[right] > a[left])
{
return left;
}
else
{
return right;
}
}
}
//霍尔法快排
int Partion(int *a, int start, int end)
{
int pivot1 = GetMid(a, start, end);
Swap(&a[start], &a[pivot1]);//将合适的基准值进行交换
int left = start;
int right = end;
int pivot = a[left];
while(left < right)
{
while(left < right && a[right] > pivot)//右路先走，遇到比初始元素小的停下
right--;
while(left < right && a[left] <= pivot)//左路再走，遇到比初始元素大的停下
left++;
if(left < right)
Swap(&a[left], &a[right]);//交换两个元素，将大的甩到右边，小的甩到左边
}
if(left == right)
{
/*a[start] = a[left];
a[left] = pivot;*/
Swap(&a[left], &a[start]);//一趟结束之后对首元素与相等指针处交换数据
}
return left;//返回指针相等的位置
}
void quicksort(int *a, int start, int end)
{
if(start >= end)
return;
int pivot = Partion(a, start, end);//选择基准元素
quicksort(a, start, pivot - 1);//快排进行左右递归
quicksort(a, pivot + 1, end);
return;
}
void Print(int *a, int len)
{
assert(a);
int i = 0;
for(i = 0 ; i < len ; i++)
{
printf("%d ",a[i]);
}
printf("\n");
return;
}
int main()
{
int a[] = {5,1,4,3,9,7,2,6,8};
int len = sizeof(a) / sizeof(int);
quicksort(a, 0, len - 1);
Print(a, len);
return 0;
} 
到这里，你可能还是会有些疑惑，为什么每次都需要右指针先往左移动，为什么不是左指针向右先移动？
这是个好问题，那么我们不妨就以左边指针开始先走，设想一下，在最后一步的时候，就是左指针向右指针靠拢，但是这个时候你并不能保证右指针的值要比基准值要小，我们的目的是为了把基准值大的甩到右边，比基准值小的，甩到左边，所以最后可能会造成左边首元素要比基准值要大。如下图所示：
或许你又要问为什么右指针开始就不会发生这种情况了呢？
答案其实很简单，是因为在倒数第二轮的时候，这轮里左右指针的值也一定交换了，这时候还是以基准值作为比较，则左指针的值一定小于基准值，所以在最后一轮右指针向左靠拢时不会造成交换之后首元素大于基准值的情况。
3）挖坑法快排实现：
我们在使用霍尔法的时候，其实会发现霍尔法不是很容易理解，用起来也很容易出错，所以就有人想出来了一种优化排序，更加容易理解的挖坑法。
所谓挖坑法，其实就是和霍尔法很相似，但是理解起来会更加直观，还是以首元素为基准值，用变量key记录，那么起始坑位就在数组首元素下标。
此时右指针开始向左寻找小于key的值，找到了直接将右指针的值放到坑位里，于是右指针就被空下来，那么坑位就变为右指针此时的位置，然后左指针在向右找比key值大的数据放在坑位里，那么此时左指针被空下来，坑位变为左指针，重复以上过程，直到左右指针相遇，最后在交换相遇点的值与key值。随后递归就和霍尔法一样了。
图示过程如下：
代码实现如下：
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>
void Swap(STDataType *a, STDataType *b)//交换函数
{
assert(a && b);
STDataType tmp = *a;
*a = *b;
*b = tmp;
return;
}
int GetMid(int *a, int left , int right) //三数取中
{
assert(a);
int mid = (left + right) / 2;
if(a[left] < a[mid])
{
if(a[mid] < a[right])
{
return mid;
}
else if(a[left] < a[right])
{
return right;
}
else
{
return right;
}
}
else
{
if(a[mid] > a[right])
{
return mid;
}
else if(a[right] > a[left])
{
return left;
}
else
{
return right;
}
}
}
int Partion(STDataType *a, int start, int end)//挖坑法
{
assert(a);
int pivot = GetMid(a, start, end);
Swap(&a[start], &a[pivot]);
int left = start;//左右指针赋值
int right = end;
int tmp = GetMid(a, left, right);//由三数取中获取适合的基准值
Swap(&a[tmp], &a[left]);//交换这两个值，把基准值放在首元素位置
int key = a[left];//将Key值记录下来
int hole = left;//挖坑的坑位记录下来
while(left < right)//当左边小于右边
{
while(left < right)
{
if(a[right] > key)//右指针向左寻找小于Key的值
{
right--;
}
else
{
Swap(&a[right], &a[hole]);//找到小于Key的值之后与坑位数据交换，然后坑位变成右指针这个位置了
hole = right;
break;
}
}
while(left < right)
{
if(a[left] < key)//同理左指针向右找大于Key的值
{
left++;
}
else
{
Swap(&a[left], &a[hole]);//找到Key值之后与坑位数据交换，然后坑位就变成左指针这个位置了
hole = left;
break;
}
}
}
if(left == right)//当两指针相遇时
{
Swap(&a[hole], &key);//把基准值与指针相遇点的值进行交换，相遇点左右指针都可以
}
return left;
}
void QuickSort(STDataType *a, int start , int end)//快排
{
assert(a);
if(start > end)//当左边大于右边就没必要再排序了
return;
int pivot = Partion(a, start, end);//找到基准值
QuickSort(a, start, pivot - 1);//基准值左边递归
QuickSort(a, pivot + 1, end);//基准值右边递归
return;
}
void Output(int *a, int len)//输出数组内容
{
assert(a);
int i = 0;
for(i = 0 ; i < len ; i++)
{
printf("%3d",a[i]);
}
printf("\n");
return;
}
void Test()
{
int a[] = { 8, 9, 5, 4, 3, 2, 7, 1, 6 };
int len = sizeof(a) / sizeof(int);
QuickSort(a, 0, len);
Output(a, len);
}
int main()
{
Test();
return 0;
}
挖坑法与霍尔法一样都需要右指针先查找值，也需要三数取中。
4）双指针快排实现：
有些人觉得霍尔大佬和挖坑法还是不太容易理解，写起来也很麻烦，所以就诞生了一种很简便的快排实现方式---双指针法，代码量少，容易理解，于是这种方法就开始流行起来。
双指针法实现的很巧妙，首先需要一个Key值记录一个基准值，通常我们选取的基准值为数组首元素为基准值，使用两个指针（slow, fast）slow指针初始位置在首元素下标，fast指针初始位置在slow的下个元素的下标。
首先右指针向右走，当遇到比Key值小的元素slow指针+1然后交换这两个指针的值，这样就能保证小于Key值的在左边，大于Key的值在右边，最后在交换首元素与slow指针的值，这一趟预排序就完成了。
双指针法图示如下：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<stdbool.h>
void Swap(int *a, int *b)
{
assert(a);
int tmp = *a;
*a = *b;
*b = tmp;
return;
}
int GetMid(int *a, int left , int right) //三数取中
{
assert(a);
int mid = (left + right) / 2;
if(a[left] < a[mid])
{
if(a[mid] < a[right])
{
return mid;
}
else if(a[left] < a[right])
{
return right;
}
else
{
return right;
}
}
else
{
if(a[mid] > a[right])
{
return mid;
}
else if(a[right] > a[left])
{
return left;
}
else
{
return right;
}
}
}
int Partion(int* a, int left, int right)
{
int pivot = GetMid(a, left, right);
Swap(&a[left], &a[pivot]);
int slow = left, fast = slow + 1;//确定快慢指针
int keyi = left;//将基准值保存
while(fast <= right)//保证快指针不越界
{
if(a[fast] < a[keyi] && ++slow != fast)//当快指针的值小于keyi的值的时候交换，同时要保证指针不与自己交换
{
Swap(&a[fast], &a[slow]);//交换值
}
++fast;//快指针向后走
}
Swap(&a[keyi], &a[slow]);//最后将基准值与慢指针交换
return slow;
}
void quickSort(int *a, int start, int end)
{
assert(a);
if(start > end)
return;
int pivot = Partion(a, start, end);
quickSort(a, start , pivot - 1);
quickSort(a, pivot + 1, end);
return;
}
void Print(int *a, int len)
{
assert(a);
int i = 0;
for(i = 0 ; i < len ; i++)
printf("%3d",a[i]);
printf("\n");
return;
}
void Test()
{
int a[] = { 9, 8, 3, 1, 7, 6, 2, 4, 5 };
int len = sizeof(a) / sizeof(int);
quickSort(a, 0, len - 1);
Print(a, len);
return;
}
int main()
{
Test();
return 0;
}
以上是快排的三种递归实现方式，但是由于在处理大量数据的时候，可能会爆系统栈，所以这时需要非递归方法来处理快排。
三、快排非递归实现
虽然现在编译器优化了很多，release版本下不是很容易爆栈，但是不排除有些情况需要非递归的方式，而且面试官也是比较喜欢问排序的非递归问题的，很多时候都是现场手撕。
其实非递归的实现方式也很简单，可以使用霍尔、挖坑或者双指针法来确定基准元素，只是递归方式变成了栈模拟实现的方式。
首先需要一个栈，初始化一个栈，这时候先入首元素下标，再入尾元素下标，当栈不为空的时候，那么取出这两个值给两个指针（left, right）同时Pop出这两个元素，此时这两个指针就是数组的区间，随后开始选取基准值(pivot)用Key记录，在Pop出左区间[left, pivot - 1], 然后入左区间的下标值，继续选取基准值，Pop出左区间，左区间全部递归完成，此时在对右区间进行处理，过程和左区间的过程相同，都是选取基准值在出栈和入栈，这里的出栈入栈就是在模拟递归的过程。当栈为空的时候，表示这个时候已经递归完成了，排序也就完成了。
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>
typedef int STDataType;
typedef struct Stack{
STDataType *a;
int top;
int capacity;
}ST;
ST *InitNewST(int n)
{
ST *p = (ST *)malloc(sizeof(ST));
p -> a = (STDataType *)malloc(sizeof(STDataType) * n);
p -> top = -1;
p -> capacity = n;
return p;
}
void StackPush(ST* st, STDataType x)
{
assert(st);
if(st -> top == st -> capacity)
{
STDataType *tmp = (STDataType *)realloc(st -> a, sizeof(STDataType) * 2 * st -> capacity);
if(tmp == NULL)
{
perror("realloc");
exit(-1);
}
st -> a = tmp;
printf("Expand %d to %d success!\n",st -> capacity, st -> capacity * 2);
st -> capacity *= 2;
}
st -> a[++st -> top] = x;
return;
}
void StackPop(ST *st)
{
assert(st);
if(st -> top >= 0)
st -> top -= 1;
}
bool EmptyStack(ST *st)
{
assert(st);
return st -> top == -1;
}
STDataType StackTop(ST *st)
{
if(!EmptyStack(st));
return st -> a[st -> top];
}
void DestroyST(ST *st)
{
assert(st);
free(st -> a);
st -> a = NULL;
free(st);
st = NULL;
return;
}
void Swap(STDataType *a, STDataType *b)
{
assert(a && b);
STDataType tmp = *a;
*a = *b;
*b = tmp;
return;
}
int GetMid(int *a, int left , int right) //三数取中
{
assert(a);
int mid = (left + right) / 2;
if(a[left] < a[mid])
{
if(a[mid] < a[right])
{
return mid;
}
else if(a[left] < a[right])
{
return right;
}
else
{
return right;
}
}
else
{
if(a[mid] > a[right])
{
return mid;
}
else if(a[right] > a[left])
{
return left;
}
else
{
return right;
}
}
}
int Partion(int *a, int start, int end)//霍尔法
{
int pivot = GetMid(a, start, end);
Swap(&a[left], &a[pivot]);
int left = start;
int right = end;
int pivot = a[left];
while(left < right)
{
while(left < right && a[right] > pivot)//右路先走，遇到比初始元素小的停下
right--;
while(left < right && a[left] <= pivot)//左路再走，遇到比初始元素大的停下
left++;
if(left < right)
Swap(&a[left], &a[right]);//交换两个元素，将大的甩到右边，小的甩到左边
}
if(left == right)
{
/*a[start] = a[left];
a[left] = pivot;*/
Swap(&a[left], &a[start]);//一趟结束之后对首元素与相等指针处交换数据
}
return left;//返回指针相等的位置
}
void QuickSortNonR(STDataType *a, int start, int end)//快排非递归实现
{
assert(a);
int len = sizeof(a) / sizeof(int);
ST *st = InitNewST(len);
StackPush(st, end);
StackPush(st, start);
while(!EmptyStack(st))
{
int left = StackTop(st);
StackPop(st);
int right = StackTop(st);
StackPop(st);
int keyi = Partion(a, left, right);
if(keyi + 1 < right)
{
StackPush(st, right);
StackPush(st, keyi + 1);
}
if(left < keyi - 1)
{
StackPush(st, keyi - 1);
StackPush(st, left);
}
}
DestroyST(st);
return;
}
void Output(int *a, int len)
{
assert(a);
int i = 0;
for(i = 0 ; i < len ; i++)
{
printf("%3d",a[i]);
}
printf("\n");
return;
}
void Test()
{
int a2[] = { 6, 1, 2, 7, 9, 3, 5, 8, 4 };
int len2 = sizeof(a2) / sizeof(int);
QuickSortNonR(a2, 0, len2 - 1);
printf("QuickSortNonR:");
Output(a2, len2);
return;
}
int main()
{
Test();
return 0;
}
腾讯云开发者
