史上最详尽的快速排序描述【图】

快速排序的核心是要有一个基准数据temp，一般取数组的第一个位置元素。然后需要有两个指针left和right，分别指向数组的第一个和最后一个元素。

首先从right开始，比较right位置元素和基准数据。如果大于等于，则将right指针左移，比较下一位元素；如果小于，就将right指针处数据赋给left指针处（此时left指针处数据已保存进temp中），left指针+1，之后开始比较left指针处数据。

拿left位置元素和基准数据进行比较。如果小于等于，则将left指针右移，比较下一位元素；而如果大于就将left指针处数据赋给right指针处，right指针-1，之后开始比较right指针处数据…重复这个过程。

直到left和right指针相等时，说明这一次比较过程完成。此时将先前存放进temp中的基准数据赋值给当前left和right指针共同指向的位置处，即可完成这一次排序操作。

之后递归排序基础数据的左半部分和右半部分，递归的过程和上面讲述的过程是一样的，只不过数组范围不再是原来的全部数组了，而是现在的左半部分或右半部分。当全部的递归过程结束后，最终结果即为排好序的结果。

快速排序执行示意图：

/*
 * 快速排序
 *
 * 参数说明：
 *     a -- 待排序的数组
 *     l -- 数组的左边界(例如，从起始位置开始排序，则l=0)
 *     r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1)
 */
void quick_sort(int a[], int l, int r)
{
    if (l < r)
    {
        int i,j,x;

        i = l;
        j = r;
        x = a[i];
        while (i < j)
        {
            while(i < j && a[j] > x)
                j--; // 从右向左找第一个小于x的数
            if(i < j)
                a[i++] = a[j];
            while(i < j && a[i] < x)
                i++; // 从左向右找第一个大于x的数
            if(i < j)
                a[j--] = a[i];
        }
        a[i] = x;
        quick_sort(a, l, i-1); /* 递归调用，排序锚点左边部分 */
        quick_sort(a, i+1, r); /* 递归调用，排序锚点右边部分*/
    }
}