排序总结之快速排序（二）

这次介绍一下快速排序，这种排序方式相较于冒泡来说稍微复杂了一点点，不过排序效率相较于冒

泡要快一些。

先讲一下这种排序方式的原理。
这次排序主要是找一个关键字privokey，然后以这个字为基准，比它小的放左边，比它大的放右边

。例如，一个数组，num[]={5, 4, 7, 2, 3, 8};如果privokey为5，则第一趟快速排序结束后，则

会变成如下所示：4 2 3 （5） 7 8；然后这个数组再分出两个数组分别进行比较，num1[]={4, 2,

3};num2={7, 8};这样一直下去即可，因为可能会有两个或者更多的比较同时进行，那么相较于冒泡

排序效率高的原因相信大家也已经明白了吧。

至于如何进行比较排序，下面以一趟快速比较详细说明。

对一组数，有两个指针low, high分别指向这个数组的头尾

实例说明，如下所示，
49,38,65,97,76,13,27,49  （是不是很熟悉，嘿嘿~ 数据结构课本上的例子哦~~）
low=0, high=7;privokey=num[low]=num[0]=49;

while(low < high && num[high] >= privokey)  --high;

因为num[6]=27<49,跳出此循环，此时high=6,此时num[low]与num[high]交换位置(此时high=6,

low=0)；

然后再进行比较，while (low < high && num[low] <= privokey) ++low;

low=0,进行此循环，num[2]=65>privokey，所以当low=2的时候跳出循环，此时num[low]与num

[high]再交换位置。（此时high=6, low=2）;

以上是一次比较，此时low=2, high=6,比较结果如下：

27，38，49，97，76，13，65，49  （high=6 low=2）

以下不再详述，第二次交换后如下：

27，38，13，49，76，97，65，49   （high=5 low=3）

第三次交换：

27，38，13，49，76，97，65，49    （high=3 low=3）

此时low=high，则第一趟快速排序结束，

（27，38，13）49（76，97，65，49） （第一趟快速排序）

（13）27（38）；49；（49，65）76（97）（第二趟快速排序）

 13 27 38 49 49 49 65 76 97






以下是快速排序的C语言实现：

#include
#include

int partion (int num[], int low, int high)  //一趟快速排序
{
    int privokey;
    int temp;
    privokey = num[low];

    while (low < high)
    {
        while(low < high && num[high] >= privokey)
            --high;

        temp = num[high];
        num[high] = num[low];
        num[low] = temp;
       
        while (low < high && num[low] <= privokey)
            ++low;

        temp = num[high];
        num[high] = num[low];
        num[low] = temp;
    }

    return low;
}


void quicksort (int num[], int low, int high)
{
    int privotloc;
    if (low < high)
    {
        privotloc = partion (num, low, high);
        quicksort (num, low, privotloc-1);
        quicksort (num, privotloc+1, high);
    }
}

int main(int argc, char *argv[])
{
    int num[]={49,38,65,97,76,13,27,49};
    int i;
    for (i = 0; i < 8; i ++)
    {
        printf ("%6d", num[i]);
    }
    printf ("\n");
    quicksort (num, 0, 7);
    for (i = 0; i < 8; i ++)
    {
        printf ("%6d", num[i]);
    }
    printf ("\n");
    return 0;
}