筆者最近學習算法，學了很久也只弄懂了幾個排序算法，在這里曬一下下，作為以后參考之用。

一、為什么要研究排序問題

許多計算機科學家認為，排序算法是算法學習中最基本的問題，原因有以下幾點：

l??有時候應用程序本身需要對信息進行排序，如為了準備客戶賬目，銀行需要對支票賬號進行排序

l??很多算法將排序作為關鍵子程序

l??現在已經有很多排序算法，它們采用各種技術

l??排序時一個可以證明其非平凡下界的問題，并可以利用排序問題的下界證明其他問題的下界

l??在實現排序算法是很多工程問題即浮出水面

二、排序問題的形式化定義

輸入：由n個數組成的一個序列<a₁,a₂,……,a_n>

輸出：對輸入序列的一個排列（重排）<a₁’,a₂’,……,a_n’>,使得a₁’?≤a₂’?≤……≤a_n’

【說明】在實際中，待排序的數很少是孤立的值，它們通常是成為激勵的數據集的一個部分，每個記錄有一個關鍵字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)>。排序算法的執行對應于遍歷一條從根到葉節點的路徑。在每個內節點作比較a_i≤a_j，其左子樹決定a_i≤a_j之后的比較，其右子樹決定a_i＞a_j之后的比較。當到達一個葉節點時排序算法就已經確定了順序。要使排序算法能正確的工作，其必要條件是n個元素的n!種排列都要作為決策樹的一個葉節點出現。在決策樹中，從根到任意一個可達葉節點之間最長路徑的長度（決策樹的高度）表示對應的排序算法中最壞情況下的比較次數。對于一棵高度為h，具有l個可達葉節點的決策樹有n!?≤l≤2^h，則有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])
{
Swap(ref Array[i], ref Array[j]);//交換數據
}
}
}
}

#endregion

　　

【時間復雜度分析】選擇排序的比較操作為n(n ? 1) / 2次，交換操作介于0和n(n ? 1) / 2次之間，故其時間復雜度為Θ(n²)

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])
{
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); //迭代實現
}
}

　　

堆排序代碼如下：?

?【時間復雜度分析】調用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++) {
rand = (int) (Math.random() * tempLen) + i;
if (rand >= tempLen) {
rand = tempLen - 1;
}
temp = arr[i];
arr[i] = arr[rand];
arr[rand] = temp;
}
}

　　

　　

轉載于:https://www.cnblogs.com/08shiyan/archive/2011/07/24/2115536.html

總結

以上是生活随笔為你收集整理的排序算法[转]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。