[C#]快速排序演算法(Quick Sort Algorithm)的實現以及簡單探討
最近在找排序功能的時候順便研讀了一下其演算法，順便自己練習用C#去寫一個。根據MSDN對List<T>.Sort()的描述，其排序所使用的方法和Array.Sort()一樣都是使用Quick Sort來做排序。
Quick Sort在一般情況下排序所需的時間為O(n log n)，最糟的情況下是O(n^2)，n是陣列的元素數量。有趣的是，最糟的情況大部分是所需要排序的陣列已經排序過了，這部份我尚未實驗過，有研究過的麻煩請和大家說一下實際的狀況是否真的如此。
下面是C#的程式碼
static void QuickSort1(int[] array, int left, int right)
{
if (left < right)
{
int i = left; int j = right + 1; while (true) { while (i + 1 < array.Length && array[++i] < array[left]) ; while (j - 1 > -1 && array[--j] > array[left]) ; if (i >= j) break; Swap(array, i, j);
} Swap(array, left, j); QuickSort1(array, left, j - 1); QuickSort1(array, j + 1, right); }
}其實主要是參考這篇而來的(我發覺他的程式碼最簡潔)。
在練習的過程中發現到很有趣的點：上面程式碼的while本身並沒有主體(body)，但是設了中斷點實際執行之後會發現它還是會自動找到符合條件的值。原來作者巧妙的利用了前置運算子(這樣翻譯不知道對不對，有錯請糾正，原文是Prefix Increment Operator)去省略了寫在body中的程式碼。我之前有簡單提過prefix和postfix的差別，簡單的說就是前置運算子回先把自身+1之後再做運算，而後置運算子則是做完運算之後才+1。作者把前置運算子應用在這個地方實在是太妙，整個程式碼就便得很簡潔，這點要學起來。
自己練習實現各個演算法的過程中可以學到不少的東西，除了可以更加瞭解這個演算法的精神(前人辛苦的結晶)之外，還可以經由寫程式的過程、參觀/比較別人寫好的程式碼來鍛鍊自己程式的功力，並且訓練邏輯思考的能力。知道要用遞迴的方式排序，那要怎麼寫遞迴才是正確的？真正動手了才會去想，用看的是騷不到這個癢處的。
這個網站有不少有趣的演算法討論以及實際的程式碼實現，有興趣的可以去複習一下自己以前學過的演算法，說不定又有新的發現及功力提昇喔。
11/4/2009 更新
我上面提到的那個演算網站提供了三種Quick Sort的演算法(主要是在軸的選取不同)，這邊補上我implement的另兩種
第二種：軸在中間
static void QuickSort2(int[] array, int left, int right){ if (left < right) { int i = left - 1; //left margin int j = right + 1; //right margin int axle = array[(left + right) / 2]; //axle while (true) { while (array[++i] < axle) ; while (array[--j] > axle) ; if (i >= j) break; Swap(array, i, j); } QuickSort2(array, left, i - 1); QuickSort2(array, j + 1, right); }}第三種：軸在最右邊 （這邊的和它提供的有點不同，我改了一下）
static void QuickSort3(int[] array, int left, int right){ if (left < right) { int i = left - 1; int j = left; int axle = array[right]; //axle while (true) { while (i < right && array[++i] < axle) ; while (j < right && array[++j] > axle) ; if (i == right || j == right) break; Swap(array, i, j); } Swap(array, right, i); QuickSort3(array, left, i - 1); QuickSort3(array, i + 1, right); }}奇怪的是經過我多次的試驗(每次都使用亂數的陣列)，最快的還是第二種，下圖是擷取測試多次中的某次結果：
