演算法 - 快速排序法 (quick sort )

快速排序是一種排序演算法，由C. A. R. Hoare所發展的，以平均效能來說，排序 n 個項目要Θ(n log n)次比較。然而，在最壞的效能下，它需要Θ(n2)次比較。一般來說，快速排序實際上明顯地比其他Θ(n log n) 演算法更快，因為它的內部迴圈（inner loop）可以在大部分的架構上很有效率地被實作出來，且在大部分真實世界的資料，可以決定設計的選擇，減少所需時間的二次方項之可能性。

時間複雜度：最佳 - O(n logn)、最差 - O(n²)
空間複雜度：O(n logn)

快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。
步驟為：

1.從數列中挑出一個元素，稱為 "基準"（pivot），
2.重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分割結束之後，該基準就處於數列的中間位置。這個稱為分割（partition）操作。
3.遞迴地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。

遞迴的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞迴下去，但是這個演算法總會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。

以上引用自維基百科：http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F

以下利用 C# 程式碼示範：

public void sort(int l, int h, int[] s)
{
    int pivotIndex = 0;

    if (h > l)
    {
        quick(l, h, ref pivotIndex, s);
        sort(l, pivotIndex, s);
        sort(pivotIndex + 1, h, s);
    }
}

void quick(int l, int h, ref int pivotIndex, int[] s)
{
    int i, j, pivotItem;

    pivotItem = s[l];
    j = l;
    for (i = l + 1; i < h; i++)
    {
        if (s[i] < pivotItem)
        {
            j++;
            swap(ref s[i], ref s[j]);
        }
    }
    pivotIndex = j;
    swap(ref s[l], ref s[pivotIndex]);
}

void swap(ref int i, ref int j)
{
    int temp;
    temp = i;
    i = j;
    j = temp;
}

回首頁