排序算法——快速排序 快速排序过程详解

概念：

快速排序（Quicksort）是给基准值找见合适位置的排序方式。

方法：

先找见基准值，然后依次用基准值和其他数据做对比，比基准值大的放到基准值右边，比基准值小的放在基准值左边，然后对基准值左右的数据分别递归得使用如上方式。

假设有5，4，2，3，1，6，9，7，8这9个数字，需要对他们进行排序。

第一步，先找见基准值，基准值可以是任意一个数据，最简单的方式就是使用第一个数据5。

第二步，利用基准值做分割操作，将小于基准值的数都放到基准值左边，大于基准值的都放到基准值右边，因为此时选择了第一个数据当基准值所以此时第一个位置是空的，现在就需要利用这个空出的位置来做操作，

X，4，2，3，1，6，9，7，8。X代表空缺的位置，末尾记为high，首先从high开始如果小于基准值，则将此值移动到X的位置，否则让high-1，继续比较。此时8大于5，则high-1，此时用7与基准值比较，7大于5，high继续-1，直到数字1时，1小于5，将数字1移动到X所在的位置，X变为X+1，又从新的X位置开始比较，如果小于5则X+1，如果大于5则又从high处开始，依次类推，直到X=high，再依次对前半部分和后半部分使用同样的方式。

代码：

#include <stdio.h>
#define MAX_ARRAY_LEN 9


void quick_sort(int *array, int l, int r)
{
    //x 从前向后扫描位置，y 从后向前扫描位置， z基准值
    int x = l, y, z;
    if(l >= r)
    {
        return;
    }
    y = r;
    z = array[l];

    while(x < y)
    {
        while(x < y && array[y] >= z)
        {
            --y;
        }
        if(x < y)
        {
            array[x++] = array[y];
        }
        while(x < y && array[x] <= z)
        {
            ++x;
        }
        if(x < y)
        {
            array[y--] = array[x];
        }
    }
    array[x] = z;
    quick_sort(array, l, x - 1);
    quick_sort(array, x + 1, r);

    return;
}
int main(void)
{
    int array[MAX_ARRAY_LEN] = {5, 4, 2, 3, 1 ,6, 9, 7, 8};
    int i;
    for(i = 0; i< MAX_ARRAY_LEN; i++)
    {
        printf("%d ",array[i]);
    }
    printf("\n");
    quick_sort(array, 0, MAX_ARRAY_LEN);
    for(i = 0; i< MAX_ARRAY_LEN; i++)
    {
        printf("%d ",array[i]);
    }
    printf("\n");
    return 0;
}