快速排序：C语言实现-蒲公英云

一、快排概述

   快速排序是一个非常优秀且常用的排序算法，尤其是在大数据的排序应用中，最为常见。
   虽然“快速”，但逻辑也是最复杂，最难理解。本算法采用分治的思想，涉及递归和函数调用，效率是极高的。
   到底什么是“分治”？所谓分治，就是以一个数为基准，将序列中的其他数往它两边“扔”。
   以从小到大排序为例，比它小的都扔到左边，比它大的都扔到右边。然后两边分别重复这种操作，不停地分，直到每个分区的基准数的左边或右边都只剩一个数为止。此时排序完成。

二、“舞动算法”数组快排

   数组，是不擅长插入的。 所以“舞动算法”使用 “交换” 取代 “插入”。Meanwhile，链表就可以采用数组不可行的插入。下面是详细的数组快排的步骤。

代码逻辑肉眼看上去较为复杂，但对于计算机来说并不难，把自己想象成计算机，老老实实地在纸上一遍遍写就可以理解了。（前提是有耐心，步骤不要乱）

设置头尾下标 i，j：i = 0, j = n-1;
以数组第一个元素为关键数据，赋值给变量key：key = A[0];
j 开始先前搜索，j—，找到第一个小于key的值A[ j ], 将A[ j ] 和 A[ i ]交换；
然后再从 i 开始向后搜索，i++，找到第一个大于key的值A[ i ]，将A[ i ] 和 A[ j ]交换；
重复3，4，直到 i == j。此时可以确保序列中所有数都与key比较过了，且key左全部比key小，右边全部比key大。

三、 bb两小时，代码5分钟。。。。。。

/*
    使用快排排序乱序数组, 从小到大排列
*/
#include <stdio.h>
void Swap(int *, int *);    // 交换函数的声明
void MyQuickSort(int *, int, int);    // 快排函数声明
int main(void)
{
    int i;
    int A[] = {489,45,-8,48,-489,18,1,0,987,0,231,14,95,-78,-2,0,2500,798,32232,48512,465,98};
    int n = sizeof(A) / sizeof(A[0]);    // 算一下数组长度
    MyQuickSort(A, 0, n-1);        // n-1是最大元素的下标
    printf("排序的结果为\n");
    for(i=0; i<n; i++)
    {
        printf("%d\x20",A[i]);
    }
    printf("\n");
    return 0;
}
/*Swap函数体*/
void Swap(int *p, int *q)
{
    int buf;
    buf = *p;
    *p = *q;
    *q  = buf;
    return;
}
/*MyQuickSort函数体*/
void MyQuickSort(int *A, int low, int high)
{
    int i = low;
    int j = high;
    int key = A[low];
    if(low>=high)    // 终止的条件
    {
        return;
    }
    while(low<high)    // while结束表示比较了一轮
    {
        while(low<high && key<=A[high])        // 往前找
        {
            high--;
        }
        if(key>A[high])    // 交换
        {
            Swap(&A[low], &A[high]);
            low++;
        }
        while(low<high && key>=A[low])    // 向后找
        {
            low++;
        }
        if(key < A[low])
        {
            Swap(&A[low], &A[high]);
            high--;
        }
    }
    MyQuickSort(A, i,  low-1);    //    同样方式对分出来的左边部分排序
    MyQuickSort(A, low+1, j);   //  同样方式对分出来的右边部分排序
}

四、缺陷与优化

    实际上还可以加以优化：
    在排序算法中，每轮比较只有一个key值，但key的位置是不断变化的，只有比完这一轮后key的位置才固定。上面的程序中每次执行swap交换函数时，实际上交换的是key和 A\[low\] 或者key和 A\[high\], 而key的位置每次都是不一样的。所以既然key的位置是“动来动去”，所以key就不必赋值到数组中了，等最后一轮比较结束以后，它的位置不动了，再赋值到数组中。
    譬如：数组A中元素为：3 1 4 2。若按照从小到大排序，那么key = 3，按上面的做法就是3 和 2 互换。2赋值给 A\[0\] 是必须的，但key就没有必要赋值给 A\[3\] 了。但你可以想象，key在 A\[3\] 这个位置，此时序列变成 2 1 4 2 (key)。
    key 再与 1 进行比较，不交换；key再与 4 比较，将 4 赋值给 A\[3\] ，然后想象 key 在4 的位置上，即此时序列变成 2 1 4(key) 4。 此时 key 左边全是比 key 小的，key 右边全是比它大的。此时 key 的位置就固定了，再将它赋值到数组中，即2 1 3 4。
/*
    使用快排排序乱序数组, 从小到大排列
    优化版本
*/
#include <stdio.h>
void MyQuickSort(int *, int, int);    // 只有一个函数声明，swap删掉了
int main(void)
{
    int i;
    int A[] = {489,45,-8,48,-489,18,1,0,987,0,231,14,95,-78,-2,0,2500,798,32232,48512,465,98};
    int n = sizeof(A) / sizeof(A[0]);    // 算一下数组长度
    MyQuickSort(A, 0, n-1);        // n-1是最大元素的下标
    printf("排序的结果为\n");
    for(i=0; i<n; i++)
    {
        printf("%d\x20",A[i]);
    }
    printf("\n");
    return 0;
}
/*MyQuickSort函数体*/
void MyQuickSort(int *A, int low, int high)
{
    int i = low;
    int j = high;
    int key = A[low];
    if(low>=high)    // 终止的条件
    {
        return;
    }
    while(low<high)    // while结束表示比较了一轮
    {
        while(low<high && key<=A[high])        // 往前找
        {
            high--;
        }
        if(key>A[high])    // 交换
        {
            A[low] = A[high];    // 直接赋值，不用交换了
            low++;
        }
        while(low<high && key>=A[low])    // 向后找
        {
            low++;
        }
        if(key < A[low])
        {
            A[high] = A[low];    // 直接赋值，不用交换了
            high--;
        }
    }
    A[low] = key;    /* 查找完一轮后key值归位，不用比较一次就交换一次
                        此时key左右分为两部分*/
    MyQuickSort(A, i,  low-1);    //    同样方式对分出来的左边部分排序
    MyQuickSort(A, low+1, j);   //  同样方式对分出来的右边部分排序
}

五、总结

    所谓快排，就是分割成独立的两部分，其中一部分比另一部分要大 （或者小）然后再按此方法，递归地对这两部分数据分别进行快速排序，直到排序完成。
    实际上，它是对冒泡排序的一种改进，是冒泡的升级版。这种改进就体现在根据分割序列的基准数，跨越式的进行交换。正是由于这种跨越式，使得元素移动的范围变大了，而不是像冒泡一样“一格一格”地“爬行”。So，效率提升 n 个档次。

更多排序方法：

冒泡排序

选择排序

插入排序

快速排序