相信算法對於許多開發人員來說都是一大難點，之所以難，就像設計模式一樣，許多人在閱讀之後，沒有很好地理解，也不願意動手上機操作，只停留在理論的學習上面，隨著時間推移就慢慢淡忘。 有些東西，你可以發明創造，但是有些東西呢，你要麼死記硬背，要麼好好理解並動手進行練習來鞏固。搞開發的話，死記硬背沒用，好好理解火候還是差一點。最好的方式，還要在理解的基礎上多敲敲代碼，使自己即知其然，又知其所以然。 本篇只是簡單介紹快速排序算法，大牛可以從旁幫忙指點，但是請嘴下留情哦:) 快速排序算法定義 快速排序（Quicksort）是對冒泡排序的一種改進。由C. A. R. Hoare在1962年提出。 它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。 快速排序算法視頻舞蹈 這裡可以看看老外的一個非常棒的創意視頻來認識快速排序的算法是怎麼樣的(http://v.youku.com/v_show/id_XMzMyODk4NTQ4.html)，它以舞蹈的方式形象而生動地再現快速排序算法的方式。 快速排序算法講解 假設現有一組整型數據需要你用快速排序的算法來進行排序（如int[] unsort = { 3, 2, 4, 1, 7, 5}，假設以第一個數據3作為左右數據的分隔數） 那麼運行完int midPosition = QuickSort(unsort, left, right);這一句的時候，得出的數組結果是： ｛2, 1, 3, 4, 7, 5｝，並且midPosition返回數據3的索引位置（即為索引2）。 這樣之後，就可以根據3為分隔數（3的位置已經排好序），把數據分為｛2, 1｝，｛ 4, 7, 5｝兩部分，然後通過遞歸的方式進行排序。 下面的代碼我覺得很好理解，雖然在網上看到有很多可以改進的地方，但是這都不是本文的重點。本文只是入門的內容，能簡單理解，盡量簡單。畢竟要復雜些，我也寫不出來。 唯一不好理解的地方，就是怎麼去理解分隔數的位置。就我本人來說吧，以前在大學時也沒學好，以至於後面來學習的時候，總會先入為主，覺得好難好難。人有抵觸的心結在的話，做事情往往是事倍功半。 所以在我花大部分時間去理解好分隔數的位置之後，下面這種快速排序算法就能自己手動敲打出來了。理解了之後，再動手實踐能鞏固學習到的知識。 下面談談我對求分隔數位置的理解，不好的地方，歡迎大家討論。 （1）預先定好一個分隔數，默認為第一個數（如我們講到的實例3，我們假設是按照從小到大的順序排序） （2）按照先從右端和左端向中間的方式來進行排序（一趟排序只是排好分隔數的位置，並且分隔數左部分的數據都比右部分的數據要小）。 右端先開始排序，如果右端的數據比分隔數要大時，則位置不用改變。一旦出現右端的數據比分隔數要小時，則需要把右端的這個小數據挪到左邊去，具體看下面步驟說明。 並且排序方向改為從左端開始，如果左端的數據比分隔數要小時，則位置不用改變。一旦出現左端的數據比分隔數要大時，則需要把左端的這個大數挪到右邊去。 並且排序方向又改為從剛才已到達的右邊位置再進行排序。 其實說白了，就是開始時，我們從左邊拿出了一個數存給一個變量（分隔數），相當於左邊留出了一個空位，讓分隔數右邊的數（這個數小於分隔數）來存放，一旦存放了，則右邊就空出一個空位，等待分隔數左邊的數（這個數比分隔數要大）來存放，反正就這麼一直調來調去，調到沒得調了，剩下的空位就是分隔數的位置。 步驟：{ 3, 2, 4, 1, 7, 5} 第一小步：把3賦值給一個存儲的變量，假設是 int splitNum = 3 （而數組3的這個位置到時將會給比3小的數占用）。我們可以理解為數組3這個數暫時是一個空位 即：{ X, 2, 4, 1, 7, 5}，X代表空位 第二小步：拿splitNum跟右端的5來進行比較（跟右端比較的目的是什麼，當然是想把比3大的數保留在3的右邊，比3小的數放在3的左邊），5大，所以5右邊不變 即：{ X, 2, 4, 1, 7, 5} 第三小步：拿splitNum跟右端的7來進行比較，7大，所以7右邊不變 即：{ X, 2, 4, 1, 7, 5} 第四小步：拿splitNum跟右端的1來進行比較，splitNum大，所以X賦值為1（那麼原先數組1的索引位置就是一個空位） 即：{ 1, 2, 4, X, 7, 5} 第五小步：拿splitNum跟左端的1來進行比較，（跟左端比較的目的是什麼，當然是想把比3大的數放到3的右邊，比3小的數保留在3的左邊），splitNum大，所以1不變 即：{ 1, 2, 4, X, 7, 5} 第六小步：拿splitNum跟左端的2來進行比較，splitNum大，所以2不變 即：{ 1, 2, 4, X, 7, 5} 第七小步：拿splitNum跟左端的4來進行比較，4大，所以X賦值為4，（那麼原先數組4的索引位置就空出來了） 即：{ 1, 2, X, 4, 7, 5} 第八小步：由於兩天都比較完了，那X賦值為splitNum的值 即：{ 1, 2, 3, 4, 7, 5} 從而實現以3為分隔數，3左邊的數都比3右邊的數要小（按照從小到大的順序排序） 快速排序算法代碼 復制代碼 namespace Sort { class Program { static void Main(string[] args) { string result = string.Empty; int[] unsort = { 3, 2, 4, 1, 7, 5 }; result = GetPrint(unsort); Console.Write("排序前結果： "); Console.WriteLine(result); //快速排序 QuickSort(unsort, 0, unsort.Length - 1); result = GetPrint(unsort); Console.Write("排序後結果： "); Console.WriteLine(result); Console.ReadLine(); } /// <summary> /// 調用快速排序算法 /// </summary> /// <param name="unsort">待排序的整形數組</param> /// <param name="left">左邊起始點</param> /// <param name="right">右邊結束點</param> public static void QuickSort(int[] unsort, int left, int right) { if (left < right) { //獲取一次排序的中間索引位置 int midPosition = GetSplitNum(unsort, left, right); //遞歸實現 QuickSort(unsort, left, midPosition - 1); QuickSort(unsort, midPosition + 1, right); } } /// <summary> /// 獲取一次排序的中間索引位置 /// </summary> /// <param name="unsort">待排序的整形數組</param> /// <param name="left">左邊起始點</param> /// <param name="right">右邊結束點</param> public static int GetSplitNum(int[] unsort, int left, int right) { int splitNum = unsort[left]; while (left < right) { /** * 從右端開始比較 * （1）假如從右端過來的數比分隔數要大，則不用處理 * （2）假如從右端過來的數比分隔數要小，則需要挪到分隔線左邊 * */ while (left < right && splitNum <= unsort[right]) { right--; } unsort[left] = unsort[right]; /** * 從從端開始比較 * （1）假如從左端過來的數比分隔數要小，則不用處理 * （2）假如從左端過來的數比分隔數要大，則需要挪到分隔線右邊 * */ while (left < right && splitNum >= unsort[left]) { left++; } unsort[right] = unsort[left]; } //一趟比較之後，分隔數的位置就可以確認起來 unsort[left] = splitNum; return left; } /// <summary> /// 打印輸出結果 /// </summary> /// <param name="unsort">數據</param> public static string GetPrint(int[] unsort) { string result = string.Empty; foreach (int n in unsort) { if (!string.IsNullOrEmpty(result)) { result += string.Format("->{0}", n); } else { result = string.Format("{0}", n); } } return result; } } }
