【演算】快速排序法 - Quicksort

快速排序法(quicksort)是目前被認為效率最高的排序演算法(sorting algorithm)。與合併排序法(mergesort)類似，快速排序法也是利用分治法(divide and conquer，D&C)，不斷地將資料分成兩部分以解決問題的例子。


首先，快速排序法會從所有資料中選擇一個支點(pivot)(支點的挑選往往決定了快速排序法的執行效率。為了簡單起見，這裡我們都直接挑選最左邊的資料為支點)。然後，(假設我們需要將資料由小排到大)我們需要把所有小於支點的資料移動到支點之前、並把所有大於支點的資料移動到支點之後。

至於要怎麼移動呢？首先，我們先從資料的最左邊開始，尋找一個比支點還大的數字。並且同樣的，從資料的最右邊開始，尋找一個比支點還小的數字。接著，將兩筆資料交換。並重複同樣的動作，直到資料已分為「比支點小」與「比支點大」兩堆後，再將支點移動到兩者之間即可。

移動完成之後，我們將資料根據支點分割(partition)成兩份，再分別對其進行相同的挑選支點並移動的動作，直到完全排序完成為止。


舉例來說，若我們需要將以下資料由小排到大：

26 13 73 31 38

我們先從資料中挑選一個支點：

26 13 73 31 38

使「比支點小」與「比支點大」的兩堆資料分別移動至支點的兩邊：

13 26 73 31 38

將資料根據支點分成兩邊：

(13) 26 (73 31 38)

左邊的資料完成排序。從右邊的資料挑選支點：

13 26 (73 31 38)

使「比支點小」與「比支點大」的兩堆資料分別移動至支點的兩邊：

13 26 (38 31 73)

將資料根據支點分成兩邊：

13 26 (38 31) 73

接下來以此類推：

13 26 (38 31) 73

13 26 (31 38) 73

13 26 (31) 38 73

直到排序完成：

13 26 31 38 73

虛擬碼大致如下：

void quicksort(Type data[1..n], Index left, Index right)
{
    if (left >= right) { return; }

    Type pivot = data[left];

    Index i = left + 1;
    Index j = right;
    while (1)
    {
        while (i <= right)
        {
            if (data[i] > pivot)
            {
                break;
            }

            i = i + 1;
        }

        while (j > left)
        {
            if (data[j] < pivot)
            {
                break;
            }

            j = j - 1;
        }

        if (i > j) { break; }

        exchange data[i] and data[j]
    }

    exchange data[left] and data[j]

    quicksort(data, left, j - 1);
    quicksort(data, j + 1, right);
}

與先前介紹的合併排序法相同的，快速排序法比較的次數不易去計算，所以我們省略這個過程。不過需要知道的是，在最差情況時，快速排序法的執行時間會隨著資料大小為 n 的變化，形成 n² 曲線成長。

雖然看起來執行效率不佳，但是在平均情況下，快速排序法執行時間的成長速率卻只有 n log n！可見在大多數情況下，快速排序法的效率仍然是相當優秀的。


以下是使用 C 語言的實現：

#include <stdio.h>
#include <stdlib.h>

void quicksort(int *data, int left, int right);
void swap(int *a, int *b);

int main(void)
{
    int i, n, data[10];

    printf("請輸入資料筆數 n(<= 10): ");
    scanf("%d", &n);

    for (i = 0; i < n; i++)
    {
        printf("請輸入第 %d 筆資料: ", i + 1);
        scanf("%d", &data[i]);
    }

    // 執行快速排序法
    quicksort(data, 0, n - 1);

    printf("\n排序後的結果: ");
    for (i = 0; i < n; i++)
    {
        printf("%d ", data[i]);
    }

    printf("\n");
    system("pause");
}

void quicksort(int *data, int left, int right)
{
    int pivot, i, j;

    if (left >= right) { return; }

    pivot = data[left];

    i = left + 1;
    j = right;

    while (1)
    {
        while (i <= right)
        {
            if (data[i] > pivot)
            {
                break;
            }

            i = i + 1;
        }

        while (j > left)
        {
            if (data[j] < pivot)
            {
                break;
            }

            j = j - 1;
        }

        if (i > j) { break; }

        swap(&data[i], &data[j]);
    }

    swap(&data[left], &data[j]);

    quicksort(data, left, j - 1);
    quicksort(data, j + 1, right);
}

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}