筆者最近學習算法，學了很久也只弄懂了幾個排序算法，在這里曬一下下，作為以后參考之用。
一、 為什么要研究排序問題
許多計算機科學家認為，排序算法是算法學習中最基本的問題，原因有以下幾點：
l ?? 有時候應用程序本身需要對信息進行排序，如為了準備客戶賬目，銀行需要對支票賬號進行排序
l ?? 很多算法將排序作為關鍵子程序
l ?? 現在已經有很多排序算法，它們采用各種技術
l ?? 排序時一個可以證明其非平凡下界的問題，并可以利用排序問題的下界證明其他問題的下界
l ?? 在實現排序算法是很多工程問題即浮出水面
二、 排序問題的形式化定義
輸入：由 n 個數組成的一個序列 <a1 ,a2 , …… ,an >
輸出：對輸入序列的一個排列（重排） <a1 ’,a2 ’, …… ,an ’>, 使得 a1 ’? ≤ a2 ’? ≤……≤ an ’
【說明】在實際中，待排序的數很少是孤立的值，它們通常是成為激勵的數據集的一個部分，每個記錄有一個關鍵字 key, 是待排序的值，其他數據位衛星數據，它們通常以 key 為中心傳遞。
三、 相關概念
1. ????????? 排序的穩定性： 在待排序的文件中，若存在多個關鍵字相同的記錄，經過排序后這些具有相同關鍵字的記錄之間的相對次序保持不變，該排序方法是穩定的；若具有相同關鍵字的記錄之間的相對次序發生變化，則稱這種排序方法是不穩定的。
A. ??????? 穩定排序： 插入排序 、冒泡排序、雞尾酒排序、計數排序、 合并交換排序 、歸并排序、基數排序、桶排序、鴿巢排序
B. ???????? 不穩定排序：選擇排序、堆排序、希爾排序、快速排序
2. ????????? 內部、外部排序：在排序過程中，若整個文件都是放在內存中處理，排序時不涉及數據的內、外存交換，則稱之為內部排序 ( 簡稱內排序 ) ；反之，若排序過程中要進行數據的內、外存交換，則稱之為外部排序。
3. ????? 待排文件的常用存儲方式：
A. ????? 順序表： 對記錄本身進行物理重排（即通過關鍵字之間的比較判定，將記錄移到合適的位置
B. ????? 鏈表： 無須移動記錄，僅需修改指針
C. ????? 用順序的方式存儲待排序的記錄，但同時建立一個輔助表：對輔助表的表目進行物理重排（即只移動輔助表的表目，而不移動記錄本身）。
4. ????? 影響排序效果的因素
A. ????? 待排序的記錄數目 n
B. ????? 記錄的大小 ( 規模 )
C. ????? 關鍵字的結構及其初始狀態
D. ???? 對穩定性的要求
E. ????? 語言工具的條件
F. ????? 存儲結構
G. ???? 時間和輔助空間復雜度等
四、 排序算法的分類（內部排序）
1. ????????? 比較類排序：排序結果中各元素的次序基于輸入元素間的比較
A. ??????? 比較排序算法的下界
比較排序可以被抽象為決策樹。一棵決策樹是一棵滿二叉樹，表示某排序算法作用于給定輸入所做的所有比較，而忽略控制結構和數據移動。
在決策樹中，對每個節點都注明 i ， j （ 1 ≤ i ， j ≤ n ），對每個葉節點都注明排列 < π (1),? π (2), …… ,? π (n)> 。排序算法的執行對應于遍歷一條從根到葉節點的路徑。在每個內節點作比較 ai ≤ aj ，其左子樹決定 ai ≤ aj 之后的比較，其右子樹決定 ai ＞ aj 之后的比較。當到達一個葉節點時排序算法就已經確定了順序。要使排序算法能正確的工作，其必要條件是 n 個元素的 n! 種排列都要作為決策樹的一個葉節點出現。在決策樹中，從根到任意一個可達葉節點之間最長路徑的長度（決策樹的高度）表示對應的排序算法中最壞情況下的比較次數。對于一棵高度為 h ，具有 l 個可達葉節點的決策樹有 n!? ≤ l ≤ 2h ，則有 h ≥ lg(n!)= Ω (nlgn)
B. ???????? 常見的比較類排序
a) ????????? 選擇類排序：選擇排序、堆排序
b) ???????? 插入類排序：插入排序、二叉插入、兩路插入、希爾排序
c) ????????? 交換類排序：冒泡排序、雞尾酒排序、合并交換排序、快速排序
d) ???????? 歸并排序
2. ????????? 非比較類排序： 計數排序、 基數排序、 桶排序、 鴿巢排序
五、 常用的排序算法
1.????????? 比較類排序
A.??????? 選擇類排序
a)????????? 選擇排序（ Selection Sort ）——原地排序、不穩定排序
【思路】 A 中最小元素，并將其與 A[0] 中元素交換；接著找出 A 中次最小元素，并將其與 A[1] 中元素交換；對 A 中頭 n-1 個元素繼續這一過程
【代碼】
#region 選擇排序 /// <summary> /// 選擇排序 /// 最差時間復雜度 Θ(n2) /// 最優時間復雜度 Θ(n2) /// 平均時間復雜度 Θ(n2) /// 原地排序 /// 【排序過程】 /// 1、首先在未排序序列中找到最小元素，存放到排序序列的起始位置 /// 2、然后，再從剩余未排序元素中繼續尋找最小元素，然后放到排序序列末尾 /// 3、以此類推，直到所有元素均排序完畢。 /// </summary> /// <param name="Array"> 待排序的數組 </param> public static void SelectionSort( int [] Array) for ( int i = 0 ; i < Array.Length; i ++ ) for ( int j = i + 1 ; j < Array.Length; j ++ ) if (Array[j] < Array[i]) ref Array[i], ref Array[j]); // 交換數據 } #endregion
【時間復雜度分析】選擇排序的比較操作為 n(n ? 1) / 2 次，交換操作介于 0 和 n(n ? 1) / 2 次之間，故其時間復雜度為Θ (n2 )
b) ????????? 堆排序（ Heap Sort ）
?六、代碼
【二叉堆】（二叉）堆數據結構是一種數組對象，可以被視為一棵完全二叉樹。二叉堆有兩種：大頂堆和小頂堆（最大堆和最小堆）。大頂堆中每個節點的值不大于其父節點的值，這樣，堆中最大的元素就存放在根節點中。
?
?
【思路】首先將輸入數組構造成大頂堆；由于數組中最大元素為 A[0] ，將其與 A[n] 交換使其達到最終正確位置；在堆中除去 A[n] ，并將 A[1 … n] 保持為大頂堆；重復上述過程，直到堆大小降為 2 。
【代碼】由思路知堆排序中應包含構造大頂堆和保持大頂堆子程序。 MaxHeapify 方法被用來保持大頂堆，其時間復雜度為 O(lgn)
/// <summary> /// 調整數組,保持大頂堆性質 /// </summary> /// <param name="Array"> 待保持大頂堆的數組 </param> /// <param name="i"> 大頂堆的根 </param> /// <param name="HeapSize"> 堆的大小 </param> private static void MaxHeapify( int [] Array, int i, int HeapSize) int left = i * 2 ; int right = left + 1 ; int largest; if (left < HeapSize && Array[left] > Array[right]) = left; else = i; if (right < HeapSize && Array[right] > Array[largest]) = right; if (largest != i) ref Array[i], ref Array[largest]); /// <summary> /// 調整數組,保持大頂堆性質(迭代實現) /// </summary> /// <param name="Array"> 待保持大頂堆的數組 </param> /// <param name="i"> 大頂堆的根 </param> /// <param name="HeapSize"> 堆的大小 </param> private static void MaxHeapifyWithoutRecursive( int [] Array, int i, int HeapSize) while (i <= HeapSize) int left = i * 2 ; int right = left + 1 ; int largest; if (left < HeapSize && Array[left] > Array[right]) = left; else = i; if (right < HeapSize && Array[right] > Array[largest]) = right; if (largest != i) ref Array[i], ref Array[largest]); = largest; else return ;
/// <summary> /// 構造大頂堆 /// </summary> /// <param name="Array"> 待構造大頂堆的數組 </param> private static void BuildMaxHeapify( int [] Array) int HeapSize = Array.Length; for ( int i = (Array.Length - 1 ) / 2 ; i >= 0 ; i -- ) // MaxHeapify(Array, i, HeapSize); // 遞歸實現 MaxHeapifyWithoutRecursive(Array, i, HeapSize); // 迭代實現 }
堆排序代碼如下：
?【時間復雜度分析】調用 BuildMaxHeap 時間為 O(n) ， n-1 次調用 MaxHeapify ，每次時間為 O(lgn) ，故堆排序時間復雜度為 O(nlgn)
using System;namespace Algorithms
{public class Sort{static Random random = new Random();#region 交換數據/// <summary>/// 交換數據/// </summary>/// <param name="a">待交換值a</param>/// <param name="b">待交換值b</param>/// <returns>是否成功</returns>public static bool Swap(ref int a, ref int b){if (!Equals(a, b)){a ^= b;b ^= a;a ^= b;return true;}else{return false;}}#endregion#region 交換類排序#region 冒泡排序/// <summary>/// 冒泡排序（Bubble Sort）/// </summary>/// 最壞時間復雜度 O(n2)/// 最優時間復雜度 O(n)/// 平均時間復雜度 O(n2)/// 原地排序/// 不穩定排序/// 【排序過程】/// 1、比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。/// 2、對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。 /// 3、針對所有的元素重復以上的步驟，除了最后一個。 /// 4、持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。 /// <param name="Array">待排序的數組</param>public static void BubbleSort(int[] Array){for (int i = 0; i < Array.Length; i++){for (int j = Array.Length - 1; j > i; --j){if (Array[j] < Array[j - 1]){Swap(ref Array[j], ref Array[j - 1]);}}}}#endregion#region 快速排序/// <summary>/// 快速排序劃分/// </summary>/// <param name="Array">待分劃的數組</param>/// <param name="p">待分劃數組下界</param>/// <param name="r">待分劃數組上界</param>/// <returns>分劃元素位置</returns>private static int Partition(int[] Array, int p, int r){int x = Array[r];int i = p - 1;for (int j = p; j < r; j++){if (Array[j] <= x){++i;Swap(ref Array[i], ref Array[j]);}}Swap(ref Array[i + 1], ref Array[r]);return i + 1;}/// <summary>/// 快速排序/// </summary>/// 最差時間復雜度 Θ(n2) /// 最優時間復雜度 Θ(nlogn) /// 平均時間復雜度 Θ(nlogn) /// 原地排序/// 非穩定排序/// 【排序過程】/// 1、從數列中挑出一個元素，稱為 "基準"， /// 2、分割：重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分割之后，該基準是它的最后位置。 /// 3、遞歸地把小于基準值元素的子數列和大于基準值元素的子數列排序。 /// <param name="Array">待排序的數組</param>/// <param name="p">待排序數組下界</param>/// <param name="r">待排序數組上界</param>public static void QuickSort(int[] Array, int p, int r){if (p < r){int q = Partition(Array, p, r);QuickSort(Array, p, q - 1);QuickSort(Array, q, r);}}/// <summary>/// 快速排序劃分(隨機化)/// </summary>/// <param name="Array">待分劃的數組</param>/// <param name="p">待分劃數組下界</param>/// <param name="r">待分劃數組上界</param>/// <returns>分劃元素位置</returns>private static int RandomizedPartition(int[] Array, int p, int r){int i = random.Next(p, r + 1);Swap(ref Array[r], ref Array[i]);return Partition(Array, p, r);}/// <summary>/// 快速排序(隨機化)/// </summary>/// <param name="Array">待排序的數組</param>/// <param name="p">待排序數組下界</param>/// <param name="r">待排序數組上界</param>public static void RandomizedQuickSort(int[] Array, int p, int r){if (p < r){int q = RandomizedPartition(Array, p, r);RandomizedQuickSort(Array, p, q - 1);RandomizedQuickSort(Array, q, r);}}/// <summary>/// Hoare劃分/// </summary>/// <param name="Array">待分劃的數組</param>/// <param name="p">待分劃數組下界</param>/// <param name="r">待分劃數組上界</param>/// <returns>分劃元素位置</returns>private static int HoarePartition(int[] Array, int p, int r){int x = Array[p];int i = p - 1;int j = r + 1;while (true){do{--j;} while (Array[j] <= x);do{++i;} while (Array[i] >= x);if (i < j){int t = Array[i];Array[i] = Array[j];Array[j] = t;}else{return j;}}}#endregion#endregion#region 選擇類排序#region 選擇排序/// <summary>/// 選擇排序/// 最差時間復雜度 О(n2) /// 最優時間復雜度 О(n2) /// 平均時間復雜度 О(n2) /// 原地排序/// 【排序過程】/// 1、首先在未排序序列中找到最小元素，存放到排序序列的起始位置/// 2、然后，再從剩余未排序元素中繼續尋找最小元素，然后放到排序序列末尾/// 3、以此類推，直到所有元素均排序完畢。/// </summary>/// <param name="Array">待排序的數組</param>public static void SelectionSort(int[] Array){for (int i = 0; i < Array.Length; i++){for (int j = i + 1; j < Array.Length; j++){if (Array[j] < Array[i]){Swap(ref Array[i], ref Array[j]);}}}}#endregion#region 堆排序/// <summary>/// 調整數組,保持大頂堆性質/// </summary>/// <param name="Array">待保持大頂堆的數組</param>/// <param name="i">大頂堆的根</param>/// <param name="HeapSize">堆的大小</param>private static void MaxHeapify(int[] Array, int i, int HeapSize){int left = i * 2;int right = left + 1;int largest;if (left < HeapSize && Array[left] > Array[right]){largest = left;}else{largest = i;}if (right < HeapSize && Array[right] > Array[largest]){largest = right;}if (largest != i){Swap(ref Array[i], ref Array[largest]);MaxHeapify(Array, largest, HeapSize);}}/// <summary>/// 調整數組,保持大頂堆性質(迭代實現)/// </summary>/// <param name="Array">待保持大頂堆的數組</param>/// <param name="i">大頂堆的根</param>/// <param name="HeapSize">堆的大小</param>private static void MaxHeapifyWithoutRecursive(int[] Array, int i, int HeapSize){while (i <= HeapSize){int left = i * 2;int right = left + 1;int largest;if (left < HeapSize && Array[left] > Array[right]){largest = left;}else{largest = i;}if (right < HeapSize && Array[right] > Array[largest]){largest = right;}if (largest != i){Swap(ref Array[i], ref Array[largest]);i = largest;}else{return;}}}/// <summary>/// 構造大頂堆/// </summary>/// <param name="Array">待構造大頂堆的數組</param>private static void BuildMaxHeapify(int[] Array){int HeapSize = Array.Length;for (int i = (Array.Length - 1) / 2; i >= 0; i--){// MaxHeapify(Array, i, HeapSize);MaxHeapifyWithoutRecursive(Array, i, HeapSize);}}/// <summary>/// 堆排序/// 最差時間復雜度 O(nlogn) /// 最優時間復雜度 O(nlogn)/// 平均時間復雜度 Θ(nlogn)/// 原地排序/// 不穩定排序/// 【排序過程】/// 1、建立一個大頂堆/// 2、把堆首（最大值）和堆尾互換 /// 3、把堆的尺寸縮小1，并保持大頂堆/// 4、重復2號步驟，直到堆的尺寸為1 /// </summary>/// <param name="Array">待排序的數組</param>public static void HeapSort(int[] Array){int HeapSize = Array.Length;BuildMaxHeapify(Array);for (int i = Array.Length - 1; i > 0; i--){int t;t = Array[0];Array[0] = Array[i];Array[i] = t;MaxHeapifyWithoutRecursive(Array, 0, --HeapSize);//MaxHeapify(Array, 0, --HeapSize);}}#endregion#endregion#region 插入類排序#region 插入排序/// <summary>/// 插入排序(非遞歸算法)/// 平均時間復雜度 Θ(n2) /// 原地排序/// 穩定排序/// 【排序過程】/// 1、從第一個元素開始，該元素可以認為已經被排序 /// 2、取出下一個元素，在已經排序的元素序列中從后向前掃描 /// 3、如果該元素（已排序）大于新元素，將該元素移到下一位置 /// 4、重復步驟3，直到找到已排序的元素小于或者等于新元素的位置 /// 5、將新元素插入到該位置中 /// 6、重復步驟2 /// </summary>/// <param name="Array">待排序的數組</param>public static void InsertionSort(int[] Array){for (int j = 1; j < Array.Length; j++){int key = Array[j];int i = j - 1;while (i >= 0 && Array[i] > key){Array[i + 1] = Array[i];--i;}Array[i + 1] = key;}}/// <summary>/// 插入排序(遞歸算法)/// </summary>/// <param name="Array">待排序的數組</param>/// <param name="length">要排序的長度</param>public static void InsertionSort(int[] Array, int length){if (length == 0){return;}else{InsertionSort(Array, length - 1);}int key = Array[length];while (Array[length] >= key){Array[length + 1] = Array[length];--length;}Array[length] = key;}#endregion#region Shell排序/// <summary>/// Shell排序（遞減增量排序）/// </summary>/// 【排序過程】/// 1、取一個小于n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為d1的倍數的記錄放在同一個組中。/// 2、先在各組內進行直接插入排序；/// 3、然后，取第二個增量d2＜d1重復上述的分組和排序，直至所取的增量dt=1(dt＜dt-1＜…＜d2＜d1)為止。/// <param name="Array">待排序的數組</param>public static void shellsort(int[] Array){int temp;int increment; //增量 int length = Array.Length;for (increment = length / 2; increment > 0; increment /= 2){for (int i = increment; i < length; ++i){int j;temp = Array[i];for (j = i; j >= increment; j -= increment){if (temp < Array[j - increment])Array[j] = Array[j - increment];elsebreak;}Array[j] = temp;}}}#endregion#endregion#region 歸并類排序#region 歸并排序/// <summary>/// 歸并數組(使用哨兵)/// <para>歸并數組Array[lower,mid]與Array[mid+1,upper]</para>/// </summary>/// <param name="Array">待歸并的數組</param>/// <param name="lower">待歸并數組下界</param>/// <param name="mid">待歸并數組分界</param>/// <param name="upper">待歸并數組上界</param>private static void MergeWithSentinel(int[] Array, int lower, int mid, int upper){int n1 = mid - lower + 1;int n2 = upper - mid;int[] L = new int[n1 + 1];int[] R = new int[n2 + 1];int i = 0;int j = 0;for (i = 0; i < n1; i++){L[i] = Array[lower + i];}for (i = 0; i < n2; i++){R[i] = Array[mid + i + 1];}L[n1] = R[n2] = int.MaxValue;i = 0;for (int k = lower; k < upper; k++){if (L[i] < R[j]){Array[k] = L[i++];}else{Array[k] = R[j++];}}}/// <summary>/// 歸并數組(不使用哨兵)/// <para>歸并數組Array[lower,mid]與Array[mid+1,upper]</para>/// </summary>/// <param name="Array">待歸并的數組</param>/// <param name="lower">待歸并數組下界</param>/// <param name="mid">待歸并數組分界</param>/// <param name="upper">待歸并數組上界</param>private static void Merge(int[] Array, int lower, int mid, int upper){int n1 = mid - lower + 1;int n2 = upper - mid;int[] L = new int[n1];int[] R = new int[n2];int i = 0;int j = 0;for (i = 0; i < n1; i++){L[i] = Array[lower + i];}for (i = 0; i < n2; i++){R[i] = Array[mid + i + 1];}i = 0;for (int k = lower; k < upper; k++){if (L[i] < R[j]){Array[k] = L[i++];}else{Array[k] = R[j++];}if (i == n1){while (j < n2){Array[++k] = R[j++];}}if (j == n2){while (i < n1){Array[++k] = L[i++];}}}}/// <summary>/// 歸并排序/// </summary>/// 最差時間復雜度 Θ(nlogn) /// 最優時間復雜度 Θ(n) /// 平均時間復雜度 Θ(nlogn)/// 非原地排序/// 穩定排序/// 【排序過程】/// 1、申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列 /// 2、設定兩個指針，最初位置分別為兩個已經排序序列的起始位置 /// 3、比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置 /// 4、重復步驟3直到某一指針達到序列尾 /// 5、將另一序列剩下的所有元素直接復制到合并序列尾 /// <param name="Array">待排序的數組</param>/// <param name="lower">待排序數組下界</param>/// <param name="upper">待排序數組上界</param>public static void MergeSort(int[] Array, int lower, int upper){if (lower < upper){int mid = (lower + upper) / 2;MergeSort(Array, lower, mid);MergeSort(Array, mid + 1, upper);Merge(Array, lower, mid, upper);}}#endregion#endregion#region 非比較類排序#region 計數排序/// <summary>/// 獲取數組最大數/// </summary>/// <param name="Array">要取最大數的數組</param>/// <returns>數組最大數</returns>private static int GetLargest(int[] Array){int largest = 0;foreach (var i in Array){if (largest < i){largest = i;}}return largest;}/// <summary>/// 計數排序/// </summary>/// <param name="Array">待排序的數組</param>public static void CountingSort(int[] Array){int largest = GetLargest(Array) + 1;int[] B = new int[Array.Length];int[] C = new int[largest];for (int i = 0; i < largest; i++){C[i] = 0;}for (int j = 0; j < Array.Length; j++){++C[Array[j]];}for (int i = 1; i < largest; i++){C[i] += C[i - 1];}for (int j = Array.Length - 1; j >= 0; --j){B[C[Array[j]] - 1] = Array[j];C[Array[j]] = C[Array[j]] - 1;}for (int i = 0; i < Array.Length; i++){Array[i] = B[i];}}#endregion#endregion}
}
原文鏈接：http://www.cnblogs.com/kingwolfofsky/archive/2011/07/23/2115129.html
附：自己的一個隨機排序
// 隨機排序一維數組 private void RandomSort(Integer[] arr) { int temp = 0 ; int rand = 0 ; int tempLen = arr.length; // 將數組進行隨機排序 for ( int i = 0 ; i < tempLen; i ++ ) { = ( int ) (Math.random() * tempLen) + i; if (rand >= tempLen) { = tempLen - 1 ; = arr[i]; = arr[rand]; = temp;
轉載于:https://www.cnblogs.com/08shiyan/archive/2011/07/24/2115536.html
總結
以上是生活随笔 為你收集整理的排序算法[转] 的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網站內容還不錯，歡迎將生活随笔 推薦給好友。
