前言

  快速排序算法是托尼·霍尔（Tony Hoare）在1962年提出来的，他是快速排序之父，是1980年图灵奖得主。本篇文章将介绍通过递归的不同写法的方法和非递归的方法来实现简单的快速排序。

一、快速排序的基本思想

  快速排序是一种

二叉树结构

的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为

基准值(后文称也其为key)

，按照该排序码将待排序集合

分割成两子序列

，左子序列中所有元素

均小于

基准值，右子序列中所有元素

均大于

基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

  这一过程相当于二叉树的

前序

遍历，先让基准值排列在相应位置，然后分割子序列，每次分割左右子序列都排好一个基准值，然后再分割左右子序列，直到序列中只有一个元素时即为最小子问题，当每一个根都排在了相应位置，那么序列就变得有序了，所以很容易就想到了用递归来实现快速排序这一算法。

二、快速排序的递归实现

  为了简单讲述快排的思想，这里只介绍排整形数据而且是升序的方法。

（一）hoare版本

1、单趟排序方法动图

单趟排序的结果：

  我们可以看到，我们以这个区间内的最左边的元素为key，然后定义了左、右指针来指向数组的下标(这里是两个整型变量，存储下标)，先让右指针从数组右边开始向左遍历元素，当遍历到的值比key值小时停下来，然后启动左指针，从左边开始遍历数组，当遍历到的值比key值大时停下来，这个时候左指针指向数组中比key值大的数值的下标，右指针指向数组中比key值小的数值的下标，这个时候我们交换这两个值，这样小的值就被换到了前面，大的值就被换到了后面，直到左右指针相遇。当左右指针相遇时的地方就是key值应该排在的相应位置，这个时候将key和相遇的地方交换数值就完成了单趟的排序。此时发现，key左边的值都比key小，右边的值都比key大。这样我们就排好了key这个元素。

单趟排序存在的问题思考：

  这个时候我们就会思考这样一个问题：最后一次交换为什么能保证比key小的值换到了前面，如果与key交换的值是大于key的，那不就出问题了吗？但其实我们发现这种情况是不存在的，交换后的结果仍然是符合左边值的比key小，右边的值比key大。

  其原因是，我们是先让右指针先向左遍历找比key小的值，找到后才让左指针向右遍历，这样可以保证相遇的时候指向的值比key小。

  下面我们来分析一下相遇的情况。相遇的情况有两种：

  第一种情况是：当右指针停下了，左指针向右遍历时没找到比key大的值，左指针与右指针相遇，这个时候指向的值一定是比key小的。

  另一种情况是：右指针向左遍历的时候没有找到比key小的值，直接与左指针相遇了，这个时候又可以分成两种情况：

  第一种情况是：左指针没动，指向key的位置，这个时候说明key本身的位置就是其相应的位置，不需要进行移动，这里自己跟自己交换相当于没移动。

  第二种情况是：左指针先前发生过与右指针的交换，交换后左指针指向的值一定是小于key的，这个时候右指针与左指针相遇后指向的值与key值交换，可以保证交换的值比key小。

2、递归展开多个子区间进行单趟排序

  上面介绍的是单趟排序后将key排到了正确的位置上，我们要递归进行多次单趟排序，每次单趟排序选出key排到相应位置，每排好key的位置后，就将key的左右分成两个区间，再在左右区间中选出key排好后再分成左右区间，如此递归，分而治之，最后区间内只剩下一个元素时（只有一个元素可以认定为有序）或者区间内没有元素时是最小子问题。最后每个元素都排在了相应的位置上，数组就变有序了。

我们将下面这个1-9乱序数组进行递归，每次递归进行一次单趟排序排好key的位置

下面是递归展开图：

  我们可以从上面的递归展开图看到，我们每次在区间内排出好key的位置，然后再在key的左右区间进行递归，再次排出key的位置，再分成两个子区间，每次递归就排好了一个值，直到区间内只有一个元素或者没有元素时结束递归。这样下来，我们的数组就变有序了。

3、代码的具体实现

霍尔法单趟排序代码

<code>// 快速排序hoare版本 单趟排序

int PartSort1(int* a, int left, int right)

{

if (left >= right)

return 0;

//最小子问题 :

//区间内只有一个值(left == right)或者为空(left >= right)

int end = right;//先从右边往左找比key值小的数丢到前面

int begin = left;//从左边下标从右找比key大的数丢到后面

int key = left;//要排序的下标

while (begin < end)//当左右指针相遇时结束

{

//从右往左找比key小的数

while (begin < end && a[end] >= a[key])

{

end--;

}

//找到比key小的数后就从左往右找比key大的数

while (begin < end && a[begin] <= a[key])

{

begin++;

}

//交换这两个数

MySwap(&a[begin], &a[end]);//功能相当于swap

}

//出来后说明begin和end相遇了，此时该下标位置就是key值排序后所在的位置

MySwap(&a[key], &a[begin]);//将key换到相应的位置

key = begin;//更新key的下标

return key;//返回排好了的元素的下标

}

霍尔法递归代码

void QuickSort(int* a, int left, int right)

{

if (left >= right)//当只有一个元素时是最小子问题

return;

//此区间执行单趟排序

//hoare法

int key = PartSort1(a, left, right);//接收已经排好了的元素下标

//递归子区间 [left,key - 1]key[key + 1,right]

QuickSort(a, left, key - 1);

QuickSort(a, key + 1, right);

return;

}

  写完后我们可以随机生成一个数组来测试一下写的代码是否有问题。

（二）挖坑法

1、单趟排序方法动图

单趟排序后的结果：

  这里的key不再表示要排序的值的下标，而是用来存储key的值。我们首先把第一个元素的值用key保存下来，并且在第一个位置挖个坑，然后定义左右指针，像hoare版本的方法一样右指针先从右到左遍历数据，当右指针遍历到比key值小的数就停下来，并且将右指针指向的值赋值给坑位，也就是填到坑里，然后右指针就变成了新的坑位。之后启动左指针，左指针从左向右遍历数据，当左指针遍历到比key大的值就停下来，然后将其指向的值填到之前右指针指向的新的坑位里。然后右指针再次向左遍历，重复该过程，直到左右指针相遇，这个时候相遇的地方形成的坑位就是key值的位置，我们再把key填入左右指针相遇的坑里，这样key的位置就排好了。

单趟排序的问题思考：

  这个方法和上面的hoare版本都是先让右指针向左遍历找比key小的值，所以不会存在导致出现排完序后出现key值左边出现大于key的元素。

2、递归展开多个子区间进行单趟排序

  快速排序挖坑法的递归和hoare法差不多，将排好后的key值左右两边分成左右子区间进行递归。但是有一点要注意：这两种方法对同一个数组进行一次单趟排序后的数组元素位置不一定对应相同。

 我们将下面这个1-9乱序数组进行递归，每次递归进行一次单趟排序排好key的位置

如果是hoare法，排好6后元素的顺序是这样：

如果是挖坑法，排好6后元素的顺序是这样：

我们可以发现这两种单趟排序后6的左右区间的元素顺序不是一一对应的，但是都符合快速排序的思想，即6的左边元素都小于6，6的右边的元素都大于6。

递归展开图：

  3、代码的具体实现

挖坑法单趟排序代码

<code>//单趟 快速排序挖坑法

int PartSort2(int* a, int left, int right)

{

//最小子问题 :

//区间内只有一个值(left == right)或者为空(left >= right)

if (left >= right)

return left;

//先从右边往左找比key值小的数填到坑里 然后right指向的地方就变成了新坑

int end = right;

//一开始坑是最左边的元素。

//之后从左边下标从右找比key大的数填到右边的坑中。

//然后左指针指向的元素就变成了新坑.

int begin = left;

int key = a[left];//保存要排序的值

while (begin < end)//当左右指针相遇时结束

{

while (begin < end && a[end] >= key)//从右往左找比key小的值填到坑里

{

end--;

}

//此时begin位置是坑

a[begin] = a[end];//将比key小的值填入坑

while (begin < end && a[begin] <= key)//从左往右找比key大的值填到坑中

{

begin++;

}

//此时end位置是坑

a[end] = a[begin];

}

//begin和end相遇的地方是key对应的位置

a[end] = key;

return end;//返回排好位置的元素的下标

}

挖坑法递归代码

void QuickSort(int* a, int left, int right)

{

if (left >= right)//当只有一个元素时是最小子问题

return;

//此区间执行单趟排序

//hoare法

//int key = PartSort1(a, left, right);//接收已经排好了的元素下标

//挖坑法

int key = PartSort2(a, left, right);//接收已经排好了的元素下标

//递归子区间 [left,key - 1]key[key + 1,right]

QuickSort(a, left, key - 1);

QuickSort(a, key + 1, right);

return;

}

  写完后我们可以随机生成一个数组来测试一下写的代码是否有问题。

（三）前后指针法

1、单趟排序方法动图

单趟排序的结果：

  和hoare版本的排序一样，将最左边的值作为待排序的key值，然后定义了前后指针prev和cur。这里的prev和cur指针不再是一左一右遍历，而是都以最左边为起点，然后cur先向右遍历，直到cur指向的值比key小，然后prev向后走一步，交换cur和prev指向的值，然后cur再向右遍历，找比key小的值，重复以上步骤，直到cur走到尽头的下一个越界的位置，这个时候我们prev所指向的位置就是key值所对应的位置，我们再交换这两个值，key就排到了其相应的位置上。

单趟排序存在的问题思考：

  这里单趟排序是把cur找到小于key的值与prev交换，所以prev指向的值不是key自己就是比key小的数，所以最后一次将key和prev位置对换时，必定是小的数和key交换，所以不会出问题。

2、递归展开多个子区间进行单趟排序

  有了前面的铺垫，这里的递归方法也是相同的，就是单趟排序排好key的位置后，递归key的左右子区间，再次排出key，再次递归左右子区间。

  注意：这三种排key的方法都不相同，所以单趟排序同一个数组后的元素排列顺序也不尽相同。

我们将下面这个1-9乱序数组进行递归，每次递归进行一次单趟排序排好key的位置

下面是递归展开图：

3、代码的具体实现

前后指针法单趟排序代码

<code>//单趟排序 快速排序前后指针法

int PartSort3(int* a, int left, int right)//返回排好了的数据key下标

{

//最小子问题 :

//区间内只有一个值(left == right)或者为空(left >= right)

if (left >= right)

return left;

int prev = left, cur = left + 1;//前后指针

while (cur <= right)//当cur指向数组外时结束

{

//让后指针向右遍历找到比要排序的数小的值，

// 如果找到了，那就让prev先++ 如果prev和cur指向同一个地方那就不交换

// prev和cur指向不同元素就交换prev和cur的值

// 当cur走到排序的区域外时，prev的位置就是要排序的数所在的位置

if (a[cur] < a[left] && ++prev != cur)

{

MySwap(&a[prev], &a[cur]);

}

cur++;//cur指针往右走

}

//此时prev的位置就是key的位置

MySwap(&a[prev], &a[left]);

return prev;//返回排好位置的下标

}

前后指针法递归代码

void QuickSort(int* a, int left, int right)

{

if (left >= right)//当只有一个元素时是最小子问题

return;

//此区间执行单趟排序

//hoare法

//int key = PartSort1(a, left, right);//接收已经排好了的元素下标

//挖坑法

//int key = PartSort2(a, left, right);//接收已经排好了的元素下标

//左右指针法

int key = PartSort3(a, left, right);//接收已经排好了的元素下标

//递归子区间 [left,key - 1]key[key + 1,right]

QuickSort(a, left, key - 1);

QuickSort(a, key + 1, right);

return;

}

  写完后我们可以随机生成一个数组来测试一下写的代码是否有问题。

  以上就是我们的三种不同的单趟排序进行递归实现快速排序的方法，下面我们来用非递归的方法实现快速排序。

三、快速排序的非递归实现

1、栈模拟递归

    上面的递归方法都是先单趟排序将key排好到相应的位置后，以key为中心分割成两个子区间再进行单趟排序进行排序选出key，重复操作。在这个过程中，左右区间的下标是单趟排序所需要的关键信息，这个时候我们就需要用到栈的后进先出的特性来模拟递归来实现非递归的快速排序。

栈模拟递归的方法：

这里我们用上面的霍尔版的单趟排序来讲解一下栈模拟递归实现快速排序的方法

下面是其递归展开图

    在排序的一开始，我们需要对0-9这个区间进行单趟排序，所以我们需要将0和9这一组下标压入栈中，在排序时再将其0和9取出来作为左右区间下标进行单趟排序，每取一个下标就将其从栈顶删除。因为栈的后进先出特性，所以我们先压入区间的右下标再压入左下标，压入两个子区间的右区间再压入左区间，这样我们先取出来的就是区间的左下标和左区间（先对左区间进行递归，递归完左区间就开始递归右区间）了。每次取栈顶的区间进行单趟排序，单趟排序完成后又将其左右区间的下标压入栈中，直到栈为空为止结束。

然后我们再将key的左右分成子区间进行单趟排序，也就是0-4和6-9这两组下标，我们将其压入栈中。

接着我们排好0-4这个区间后，又分成了0-1和3-4这两个子区间压入栈中。

排好0-1这个区间后，因为其左右区间都为最小子区间，一个是只有单个元素和空元素，所以我们不将其区间下标压入栈中不进行单趟排序。此时我们取栈顶区间3-4进行单趟排序。

  而当我们排完3-4后就排6-9的区间，我们发现，上面的递归展开图中的左子树就排序完成了，而我们右边子树又和前面一样，将要排序的下标压入栈中，直到当栈为空时，整个数组就变有序了。

2、非递归代码

<code>// 快速排序 非递归实现 利用栈保存左右下标的值进行快排

void QuickSortNonR(int* a, int left, int right)

{

//下面用到的栈是自己手搓的

//建立栈

Stack stack;

//初始化栈

StackInit(&stack);

//将一组左右下标压入栈

//先将右下标压入栈再压入左下标 先压入右区间再压入左区间

//由于后进先出的关系，这样可以保证先取到的栈顶元素是对应左下标 先递归的区间是左区间的

StackPush(&stack, right);

StackPush(&stack, left);

//这三个变量和上面的霍尔单趟排序的变量作用相同

int begin;//从左边开始往右遍历找比key值大的元素

int end;//从右边开始往左遍历找比key值小的元素

int key;//要排序的值的下标

while (!StackEmpty(&stack))//当栈为空时结束循环

{

begin = StackTop(&stack);//得到要排序左下标

left = begin;//保存左边界下标

StackPop(&stack);

end = StackTop(&stack);//得到要排序右下标

right = end;//保存右边界下标

StackPop(&stack);

key = left;//要排序的下标

//这里和上面写的霍尔单趟排序相同，进行单趟排序将key排到对应位置

while (begin < end)//当左右指针相遇时结束

{

//从右往左找比key小的数

while (end > begin && a[end] >= a[key])

{

end--;

}

//找到比key小的数后就从左往右找比key大的数

while (end > begin && a[begin] <= a[key])

{

begin++;

}

//交换这两个数

MySwap(&a[begin], &a[end]);

}

//出来后说明begin和end相遇了，此时该下标位置就是key值排序后所在的位置

MySwap(&a[key], &a[begin]);

key = begin;//将key的下标更新到排好了的位置的下标

//将要递归排序的区域压入栈

//[left,key - 1] key [key + 1,right]

//如果区间内只有一个元素或没有元素就不压入栈

//将分成的两个子区间的右区间压入栈中

if (key + 1 < right)//由于后进先出的关系，这样可以让先递归的区间是左区间的

{

StackPush(&stack, right);

StackPush(&stack, key + 1);

}

//将分成的两个子区间的左区间压入栈中

if (left < key - 1)

{

StackPush(&stack, key - 1);

StackPush(&stack,left);

}

}

return;

}

  写完后我们可以随机生成一个数组来测试一下写的代码是否有问题。

四、快速排序的时间和空间复杂度分析

  虽然快速排序的实现方法有很多种，但是其时间复杂度和空间复杂都是不变的。

1、时间复杂度(nlog(n))

  根据二叉树的知识我们知道，快速排序相当于一个二叉树，假如要排序的数组有n个元素，那我们的二叉树（在使用了三数取中算法后或随机取数算法优化后）高度大概为log(n+1),每一层左右指针相遇所需要遍历一次区间，那就是n次，下一层n-1次，下下层n-2次......这里统一取n，所以我们排完整个数组需要遍历n * log(n + 1)次，所以快速排序的时间复杂度是nlog(n)。

2、空间复杂度(log(n))

  不管我们使用递归的方法实现快排还是栈非递归的方式模拟递归，都占用了一定的空间。上面分析我们知道，二叉树大概的高度为log(n+1)，因为递归需要为函数开辟函数栈帧，而函数栈帧释放后可以被其他递归重复利用，所以所开辟的空间大小也就是树的高度log(n+1)。我们用栈存储下标也需要开辟这么多空间，所以空间复杂度为log(n)。

五、快速排序的优化算法

1、三数取中和随机取数优化算法

  在上面的快速排序中，如果排序的数是极其混乱的，那么在效率上看不出什么问题，但如果我们排序的一组数据是下面这组数据的话,就会发现很明显的问题。

其递归展开图

  我们发现这个二叉树的形状极其不均匀，每次递归只有右区间而没有左区间。二叉树的高度和要排序的数组个数一致，也就是数组有n个元素，那二叉树的高度就为n，根据上面对时间复杂度的分析，时间复杂度为o(n²)。

  如果我们一开始排序的key不是1而是5，那么我们就可以让其分成的子区间变得均匀。同理，如果排序1-4时，我们排序的key是2而不是1，这个区间分成的子区间就可以变得均匀。我们有随机取数算法和三数取中优化算法来解决这个问题。

随机取数法

  这个方法就是从左右区间中随机取一个元素作为key值来排序，因为是随机的，所以取到的值有很小的几率是边缘的值，这样可以让我们的二叉树不那么偏向一侧。

代码实现：

<code>void QuickSort(int* a, int left, int right)

{

if (left >= right)//当只有一个元素时是最小子问题

return;

//优化算法

//随机取数优化算法

int rand_index = left + rand() % (right - left + 1);//在区间内随机选一个元素

MySwap(&a[left], &a[rand_index]);//将随机选到的元素与最左边的元素交换作为要排序的key值

//此区间执行单趟排序

//hoare法

//int key = PartSort1(a, left, right);//接收已经排好了的元素下标

//挖坑法

//int key = PartSort2(a, left, right);//接收已经排好了的元素下标

//左右指针法

int key = PartSort3(a, left, right);//接收已经排好了的元素下标

//递归子区间 [left,key - 1]key[key + 1,right]

QuickSort(a, left, key - 1);

QuickSort(a, key + 1, right);

return;

}

三数取中法

  顾名思义就是在三个数中找一个中间值作为key值来排序，也就是在区间中选三个数，分别是左边界下标、右边界下标、和区间的中间下标这三个数进行比较，将数值大小介于两者之间的数作为key值排序，这样可以保证让key值排好后的位置靠近中间。

代码实现：

三个数中得到中间数的函数

//三数取中优化代码

int GetMidIndex(int*a,int left,int right)//传入数组和区间的左右下标

{

int mid = (left + right) / 2;

if (a[left] <= a[right])// left right

{

if (a[mid] >= a[right])

return right;

else if (a[mid] <= a[left])

return left;

else

return mid;

}

else//right left

{

if (a[mid] >= a[left])

return left;

else if (a[mid] <= a[right])

return right;

else

return mid;

}

}

具体优化代码:

void QuickSort(int* a, int left, int right)

{

if (left >= right)//当只有一个元素时是最小子问题

return;

//随机取数优化算法

//int rand_index = left + rand() % (right - left + 1);//在区间内随机选一个元素

//MySwap(&a[left], &a[rand_index]);//将随机选到的元素与最左边的元素交换作为要排序的key值

//三数取中优化算法

int mid_index = GetMidIndex(a, left, right);//得到三个数中的中位数

MySwap(&a[left], &a[mid_index]);

//此区间执行单趟排序

//hoare法

//int key = PartSort1(a, left, right);//接收已经排好了的元素下标

//挖坑法

//int key = PartSort2(a, left, right);//接收已经排好了的元素下标

//左右指针法

int key = PartSort3(a, left, right);//接收已经排好了的元素下标

//递归子区间 [left,key - 1]key[key + 1,right]

QuickSort(a, left, key - 1);

QuickSort(a, key + 1, right);

return;

}

  上面的这两种优化算法都是针对这种顺序不是很乱而比较接近有序的数组的优化，可以减少出现最坏的情况的几率。上面我只对递归的快速排序进行了三数取中和随机取数的优化，而我们的非递归的快速排序也可以采用其方法进行优化。

2、小区间使用插入排序优化递归次数

  这个优化方法可以减少递归的次数，只针对递归的优化。

  在一个理想的均匀二叉树中，我们知道最后一层的叶子个数占据整个二叉树节点个数的一半，二叉树最后三层的节点个数加起来差不多接近整个二叉树的节点个数，最后这几层的二叉树要排序的区间较小，如果我们可以让最后这几层节点不进行递归排序，而是使用别的排序方法排序，就可以减少递归的次数，这个时候我们可以通过在小区间内使用插入排序来减少递归次数，插入排序适合排序元素个数较少的数组。

  具体代码实现：

void QuickSort(int* a, int left, int right)

{

if (left >= right)//当只有一个元素时是最小子问题

return;

//优化算法

//如果区域内元素少于17那就执行插入排序减少递归次数

//最后三层的子区间大小

//倒数第三层 16 / 2 = 8

//倒数第二层 8 / 2 = 4

//倒数第一层 4 / 2 = 2

if (right - left + 1<= 16)

{

InsertSort(a + left, right - left + 1);//插入排序 传入数组和数组要排序的个数

return;

}

//随机取数优化算法

//int rand_index = left + rand() % (right - left + 1);//在区间内随机选一个元素

//MySwap(&a[left], &a[rand_index]);//将随机选到的元素与最左边的元素交换作为要排序的key值

//三数取中优化算法

int mid_index = GetMidIndex(a, left, right);//得到三个数的中位数

MySwap(&a[left], &a[mid_index]);

//此区间执行单趟排序

//hoare法

//int key = PartSort1(a, left, right);//接收已经排好了的元素下标

//挖坑法

//int key = PartSort2(a, left, right);//接收已经排好了的元素下标

//左右指针法

int key = PartSort3(a, left, right);//接收已经排好了的元素下标

//递归子区间 [left,key - 1]key[key + 1,right]

QuickSort(a, left, key - 1);

QuickSort(a, key + 1, right);

return;

}

  以上就是对快速排序的实现方法简介、优化以及排序的效率分析。快速排序是托尼·霍尔（Tony Hoare）在1962年提出来的，我们学习快排算法思想，可以提高我们的思考能力。