前言

继续我的填坑旅程，上次说到《排序算法系列之（二）——冒泡排序名字最为形象的一个》2017-09-16 10:42:07，又过了半年多，终于再一次鼓起勇气决定聊一聊快速排序的思路，不过与冒泡排序不同的是，这个快速排序的名字似乎和算法的思路没有什么关系，这个名字太抽象了，起这个名字可能当初仅仅是因为它比别的排序快一点。咳咳！

抽象的名字不利于我们对于算法思路的理解，或许这就是我为什么当初认为快速排序是最难理解的排序算法，也可能是当初还没接触过堆排序、希尔排序等这些另类的排序吧！毕竟工作5年之后再来看这个快速排序，思路也是很清晰的，忽然发现它当初那份神秘的气息消散了许多。

快速排序

我们今天同样略过各种复杂度，直奔主题——快速排序，既然它的名字不是说算法思路，那就是说性质了，通俗点说就是在一般情况下它比选择排序、冒泡排序要快，先不用关心它为什么快，我们先来模拟一个最简单的快速排序。

快速排序的核心思想是分治、递归，将原本问题的规模不断缩小，递归求解，这类算法往往代码很简单，但是理解起来难度大一点，说一下总体思路，我们先来举个例子。假设将N个数从小到大排序，首先是在等待排序的数组N中随便选一个数M，为了简单我们选择第一个，然后遍历待排数组，把比M小的数放到M的左边，把比M大的数放到M的右边，一次遍历结束M左边有m1个数，右边有m2个数(m1+m2+1=N)，然后就形成了两个待排数组N1和N2，对于每个待排数组重复上述操作，直到待排数组缩小到一个数字，则待排数据排序完毕，整个数组变为有序。

因为这个排序比较抽象，所以前面的橘子、苹果的例子很难解释清楚，但是我们可以用标了号的橙子来理解，是不是感觉橙子伟大了一点，为什么橙子可以，因为早上刚刚吃过橙子，嗯！就是这么任性！假设桌上摆着一排橙子，他们的重量分别是6, 2, 7, 3, 8, 9，什么？你问我重量单位是什么，那就是斤吧，谁叫这些橙子变异了呢，大的大，小的小，好了，能帮助我们理解算法就好了，自从有了转基因，今后多重的橙子都可能遇到。

事先解释一下，我们这些橙子在桌上排成了一排，并且每一个橙子都放在了盘子里，盘子不移动，我们只移动盘子里的橙子，空盘子用*表示，手里的橙子用M表示，为了省点力气，我们尽可能的少移动橙子。

起初桌子上盘子里的橙子情况是这样的:
6, 2, 7, 3, 8, 9，M=*
用手拿起第一个盘子里的橙子后：
*, 2, 7, 3, 8, 9 ，M=6
从后往前找到第一个比M小的橙子放到前面，9、8、3，发现3是第一个符合条件的，把它拿到前面的盘子，变成了这样：
3, 2, 7, *, 8, 9 ，M=6
然后第一个不算从前往后找到第一个比M大的橙子放到后面，2、7，发现7是第一个符合条件的，把它放在后面的空盘子：
3, 2, *, 7, 8, 9 ，M=6
到此为止，我们已经把所有位置都遍历一遍了，这就是所谓的一趟排序，如果中间还有位置没有比较，重复步骤3和步骤4，直到所有的位置的橙子都被遍历到，把M=6放到最后的空盘子中就变成了：
3, 2, 6, 7, 8, 9 ，M=*
执行到这个步骤，原来的这些橙子就被分成了两部分，比M=6小的放到了它的前面，比M=6大的放到了它的后面，现在就变成了两个规模较小的数组排序，我们以前面的待排数组N1为例，重复步骤2，先取出第一个橙子，拿在手里：
*, 2 ，M=3
重复步骤3，从后往前找到第一个比M小的橙子放到前面，发现2这个橙子，然后把它放到前面的空盘子，现在的情况如下：
2, * ，M=3
本来应该重复步骤4，但是此时发现所有的位置已经遍历过了，所以步骤4省略，直接步骤5，把M=3放在空盘子中：
2, 3 ，M=*
此时被M=3分割的就过只有一部分，并且不大于一个橙子，所以左半部分排序结果，总体来看顺序为：
2, 3, 6, 7, 8, 9 ，M=*
接着就要对步骤5后面的右半部分排序了，也就算是对7, 8, 9，虽然现在数据少我们一眼就能看出这结果数是有序的，但是如果在程序代码中，还是会对这部分橙子重复步骤3、4、5来达到有序，这里就不再逐步解释了，最后的结果就是：
2, 3, 6, 7, 8, 9 ，M=*

代码实现

/*
功能： 快速排序，实现数组元素从小到大排列
参数： array--表示待排序的数组，此处会退化成指针
        low  --待排序区间的起始索引
        high --待排序区间的结束索引
返回值：无
注意： 只用来表示思路，不考虑指针为空等特殊情况
*/
void quick_sort(int array[], int low, int high)
{
    if (low >= high)
        return;

    int front = low, back = high, key = array[low]; // 选取第一个元素作为中轴
    while (front < back)
    {
        while (front < back && array[back] >= key)
            --back;
        array[front] = array[back];     // 从后面找到第一个比中轴小的交换

        while (front < back && array[front] <= key)
            ++front;
        array[back] = array[front];     // 从前面找到第一个比中轴大的交换
    }

    array[front] = key;
    quick_sort(array, low, front - 1);  // 递归快排前半段
    quick_sort(array, low, front + 1);  // 递归快排后半段
}

代码分析

上述代码与橙子排序的示例思路完全一致，key = array[low]是步骤2，选取第一个元素作为中轴；最外层的while循环是反复重复步骤3和步骤4，保证遍历所有位置的橙子；内部的第一个while循环是步骤3，从后面找到第一个比中轴小的；内部的第二个while循环是步骤4，从前面找到第一个比中轴大的；array[front] = key;就是步骤5，把手里的橙子放回到空盘子中；接下来的两个函数调用都是调用自己，也就是递归调用，分别处理小于M的一段和大于M的一段，怎么样？代码是不是好理解多了？如果觉得我理解的有问题或者代码有错，也欢迎大家批评指正。

运行测试

快速排序–源码

如果你想运行测试一下，可以复制或者下载源代码，在本机运行测试一下，当然也可以选择在线编辑器，这是我新发现的在线编译器，样子还挺好看的，把源代码复制到网页中运行查看结果。