2分鐘看懂快速排序的算法

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

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

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



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

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

先把他記下來(lái)。

?

然后從 y 開(kāi)始，4比3大，不用管，y 向前移動(dòng)。

?

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

?

6比 3 大，放在后面，y 向前移動(dòng)。

?

0比3小，放在前面，x向后移動(dòng)。

?

7比3大，放在后面，y 向前移動(dòng)。

?

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



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

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

搞清楚了原理還不夠，作為求職者把代碼寫(xiě)出來(lái)才是王道。

#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;
}

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

冒泡排序：

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

快速排序：

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

要說(shuō)原因的話(huà)，冒泡排序只能相鄰位置上比較移動(dòng)，但是快速排序卻可以跳著來(lái)，所以大部分情況下，快速排序效率都要高于冒泡排序。

審核編輯：劉清