C#實現快速排序

網上很多關於快速排序的教程，嗯，不錯，版本也很多，有的試了一下還報錯。。呵呵

於是乎低智商的朕花了好幾天廢了8張草稿紙才弄明白。。

快速排序的采用的分治啊挖坑填數啊之類的網上到處都是，具體過程自己百度吧，這裡就講講我自己寫的代碼。還有，快排是一種不穩定的排序算法，就是說，當整個數列是無序狀態時，效率高，但是，當把一個從大到小的通過排序轉成從小到大的，那就呵呵了，隨時StackOverflow。。

OK，先上代碼（排序結果是從小到大）

         static void QuickSort(int[] num, int left, int right)
         {
             if (left >= right)
                 return;
 
             int key = num[left];
             int i = left;
             int j = right;
 
             while (i < j)
             {
                 while (i < j && key < num[j])
                     j--;
                 if (i >= j)
                 {
                     num[i] = key;
                     break;
                 }
                 num[i] = num[j];
 
                 while (i < j && key >= num[i])
                     i++;
                 if (i >= j)
                 {
                     num[i] = key;
                     break;
                 }
                 num[j] = num[i];
             }
             num[i] = key;
 
             QuickSort(num, left, i - 1);
             QuickSort(num, i + 1, right);
         }

參數中的num就不用說了吧，left和right分別代表排序待排序數組的開始和結尾的索引，當然默認排序整個數組的話就：

QuickSort(a, 0, a.Length - 1);

假設待排序數組是a，排序索引是0到最後一項的元素。

快排使用分治，選取一個關鍵值key（代碼中的第6行，並且默認使用待排序數組的第一個值），把比它大的和比它小的分別放在兩邊。

具體就是先從數組右邊（j值記錄的索引）開始找比key小的數，對應代碼的12、13行，至於為什麼要i < j，呵呵，待會兒說。

循12行環的意義是，如果當前num[j]比key大，j就自減，直到key>num[j]就找到了比key小或相等的數了呗。

又由於排序的數千變萬化，所以有的情況下j一路減下去或記錄左邊索引的i一路加上去，就有可能i>=j，於是就有了10、12、14、21、23行判斷i和j關系的語句了，因為如果i都>=j了，就表示分完了啊。

 於是先假設i一直<j，通過12行的循環找到了比key小或等於的值，就把左右的數交換，不用擔心key不見，因為有第6行。。

之後又通過21行的循環找比key大的值，再在28行交換。這樣下來10行的大循環完了之後，數組就留了一個“空位”（這個“空位”當然有數，只是它應該被key填充），再在30行用key填充。

之後31、32行遞歸（別說你不知道啥意思），再對key兩邊的數進行排序。

排序完成後，i值就對應key的索引，所以遞歸調用的參數就那樣填。。

以上純屬個人理解，有錯誤的地方還請指出！