之前有同學(xué)提出想要復(fù)習(xí)一下排序算法，那我們今天就挑一個難度中等的，快速排序。

先搞清楚快速排序原理，然后再寫代碼。

快速排序的原理不難，先找到一個數(shù)字，我們把它稱作基準，然后通過一系列的比較交換，能讓基準達到一個合適的位置，保證基準前面的數(shù)字都比他小，后面的數(shù)字都比他大。



這個過程需要兩個指針 x 和 y，其實就是數(shù)組的下標，x指向數(shù)組第一個數(shù)字，y指向數(shù)組最后一個數(shù)字。

為了操作方便，我們一般以第一個數(shù)字為基準。

先把他記下來。

?

然后從 y 開始，4比3大，不用管，y 向前移動。

?

2比 3 小，比基準小的數(shù)字應(yīng)該放在左邊，所以把 2 移動到前面，同時 x 向后移動。

?

6比 3 大，放在后面，y 向前移動。

?

0比3小，放在前面，x向后移動。

?

7比3大，放在后面，y 向前移動。

?

最后，x 和 y 相等，把3放到這個位置上。



第一輪移動結(jié)束?，F(xiàn)象就是，3的前面都是比3小的，3的后面都是比3大的。

接下來就是對3的前面和3的后面做同樣的操作，我們應(yīng)該立馬能想到遞歸。

搞清楚了原理還不夠，作為求職者把代碼寫出來才是王道。

#include 


void quick_sort(int *a, int start, int end)
{
    if (start >= end)
        return;


    int x = start;
    int y = end;
    int base = a[start];


    while (x < y)
    {   
        while (a[y] > base && x < y)
        {   
            y--;
        }   


        if (x < y)
        {
            a[x++] = a[y];
        }


        while (a[x] < base && x < y)
        {
            x++;
        }


        if (x < y)
        {
            a[y--] = a[x];
        }
    }


    a[x] = base;


    quick_sort(a, start, x - 1);
    quick_sort(a, x + 1, end);
}


int main()
{
    int array[] = {3, 6, 7, 0, 2, 4};


    quick_sort(array, 0, 6);


    for (int i = 0; i < 6; i++)
    {
        printf("%d ", array[i]);
    }


    return 0;
}

快速排序是不是真的很快？ 我們可以和冒泡排序做個對比，修改下代碼，隨機產(chǎn)生5萬個數(shù)據(jù)，使用冒泡排序和快速排序，時間上的差別確實很大。

冒泡排序：

real  0m8.255s
user  0m8.098s
sys  0m0.008s

快速排序：

real  0m0.078s
user  0m0.010s
sys  0m0.000s

要說原因的話，冒泡排序只能相鄰位置上比較移動，但是快速排序卻可以跳著來，所以大部分情況下，快速排序效率都要高于冒泡排序。

審核編輯：劉清