各種排序算法總結及C#代碼實現
排序是計算機內經常進行的一種操作，其目的是將一組“無序”的記錄序列調整為“有序”的記錄序列。分內部排序和外部排序。若整個排 序過程不需要訪問外存便能完成，則稱此類排序問題為內部排序。反之，若參加排序的記錄數量很大，整個序列的排序過程不可能在內存中完成，則稱此類排序問題 為外部排序。內部排序的過程是一個逐步擴大記錄的有序序列長度的過程。
將雜亂無章的數據元素，通過一定的方法按關鍵字順序排列的過程叫做排序。假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序， 這些記錄的相對次序保持不變，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩定的；否則稱為 不穩定的。
分類
穩定排序：假設在待排序的文件中，存在兩個或兩個以上的記錄具有相同的關鍵字，在用某種排序法排序后，若這些相同關鍵字的元素的相對次序仍然不變，則這種排序方法是穩定的。其中冒泡，插入，基數，歸并屬于穩定排序，選擇，快速，希爾，堆屬于不穩定排序。
就地排序：若排序算法所需的輔助空間并不依賴于問題的規模n，即輔助空間為O（1）,則稱為就地排序。（百度百科）
交換排序
冒泡排序
已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先比較a[1]與a[2]的值，若a[1]大于a[2]則交換兩者的值， 否則不變。再比較a[2]與a[3]的值，若a[2]大于a[3]則交換兩者的值，否則不變。再比較a[3]與a[4]，以此類推，最后比較a[n-1] 與a[n]的值。這樣處理一輪后，a[n]的值一定是這組數據中最大的。再對a[1]~a[n-1]以相同方法處理一輪，則a[n-1]的值一定是 a[1]~a[n-1]中最大的。再對a[1]~a[n-2]以相同方法處理一輪，以此類推。共處理n-1輪后a[1]、a[2]、……a[n]就以升序 排列了。降序排列與升序排列相類似，若a[1]小于a[2]則交換兩者的值，否則不變，后面以此類推。 總的來講，每一輪排序后最大（或最小）的數將移動到數據序列的最后，理論上總共要進行n(n-1）/2次交換。
代碼實現
/// <summary>
/// 冒泡排序
/// </summary>
/// <param name="arry">要排序的整數數組</param>
public static void BubbleSort(this int[] arry)
{
for (int i = 0; i < arry.Length; i++)
{
for (int j = 0; j < arry.Length - 1 - i; j++)
{
//比較相鄰的兩個元素，如果前面的比后面的大，則交換位置
if (arry[j] > arry[j + 1])
{
int temp = arry[j + 1];
arry[j + 1] = arry[j];
arry[j] = temp;
}
}
}
}
簡單測試
class Program
{
static void Main(string[] args)
{
int[] arry = new int[] { 1, 2, 3, 4, 1, -1 };
arry.BubbleSort();
for (int i = 0; i < arry.Length; i++)
{
Console.Write("\t" + arry[i]);
}
Console.Read();
}
}
結果
這里采用的是為整型數組添加擴展方法實現的冒泡排序。
優點：穩定
缺點：慢，每次只移動相鄰的兩個元素。
時間復雜度：理想情況下（數組本來就是有序的），此時最好的時間復雜度為o(n),最壞的時間復雜度(數據反序的)，此時的時間復雜度為o(n*n) 。冒泡排序的平均時間負責度為o(n*n).
快速排序
設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用數組的第一個數）作為關鍵數據，然后將所有比它小的數都放到它前面，所 有比它大的數都放到它后面，這個過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩定的排序算法，也就是說，多個相同的值的相對位置也許會在算法結 束時產生變動。
一趟快速排序的算法是：
1）設置兩個變量i、j，排序開始的時候：i=0，j=N-1；
2）以第一個數組元素作為關鍵數據，賦值給key，即key=A[0]；
3）從j開始向前搜索，即由后開始向前搜索(j–)，找到第一個小于key的值A[j]，將A[j]和A[i]互換；
4）從i開始向后搜索，即由前開始向后搜索(i++)，找到第一個大于key的A[i]，將A[i]和A[j]互換；
5）重復第3、4步，直到i=j； (3,4步中，沒找到符合條件的值，即3中A[j]不小于key,4中A[i]不大于key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到 為止。找到符合條件的值，進行交換的時候i， j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時候，此時令循環結束）。
代碼實現
/// <summary>
/// 快速排序
/// </summary>
/// <param name="arry">要排序的數組</param>
/// <param name="left">低位</param>
/// <param name="right">高位</param>
public static void QuickSort(this int[] arry, int left, int right)
{
//左邊索引小于右邊，則還未排序完成
if (left < right)
{
//取中間的元素作為比較基準，小于他的往左邊移，大于他的往右邊移
int middle = arry[(left + right) / 2];
int i = left - 1;
int j = right + 1;
while (true)
{
//移動下標，左邊的往右移動，右邊的向左移動
while (arry[++i] < middle && i < right);
while (arry[--j] > middle && j > 0);
if (i >= j)
break;
//交換位置
int number = arry[i];
arry[i] = arry[j];
arry[j] = number;
}
QuickSort(arry, left, i - 1);
QuickSort(arry, j + 1, right);
}
}
簡單測試
static void Main(string[] args)
{
int[] arry = new int[] { 34,1,221,50,44,58,12,1,1};
//arry.BubbleSort();
arry.QuickSort(0, arry.Length-1 );
for (int i = 0; i < arry.Length; i++)
{
Console.Write("\t" + arry[i]);
}
Console.Read();
}
結果
插入排序
直接插入排序
每次從無序表中取出第一個元素，把它插入到有序表的合適位置，使有序表仍然有序。
第一趟比較前兩個數，然后把第二個數按大小插入到有序表中； 第二趟把第三個數據與前兩個數從前向后掃描，把第三個數按大小插入到有序表中；依次進行下去，進行了(n-1)趟掃描以后就完成了整個排序過程。
直接插入排序屬于穩定的排序，最壞時間復雜性為O(n^2)，空間復雜度為O(1)。
直接插入排序是由兩層嵌套循環組成的。外層循環標識并決定待比較的數值。內層循環為待比較數值確定其最終位置。直接插入排序是將待比較的數值與它的前一個 數值進行比較，所以外層循環是從第二個數值開始的。當前一數值比待比較數值大的情況下繼續循環比較，直到找到比待比較數值小的并將待比較數值置入其后一位 置，結束該次循環。
值得注意的是，我們必需用一個存儲空間來保存當前待比較的數值，因為當一趟比較完成時，我們要將待比較數值置入比它小的數值的后一位 插入排序類似玩牌時整理手中紙牌的過程。插入排序的基本方法是：每步將一個待排序的記錄按其關鍵字的大小插到前面已經排序的序列中的適當位置，直到全部記 錄插入完畢為止。
代碼實現
/// <summary>
/// 直接插入排序
/// </summary>
/// <param name="arry">要排序的數組</param>
public static void InsertSort(this int[] arry)
{
//直接插入排序是將待比較的數值與它的前一個數值進行比較，所以外層循環是從第二個數值開始的
for (int i = 1; i < arry.Length; i++)
{
//如果當前元素小于其前面的元素
if (arry[i] < arry[i - 1])
{
//用一個變量來保存當前待比較的數值，因為當一趟比較完成時，我們要將待比較數值置入比它小的數值的后一位
int temp = arry[i];
int j = 0;
for (j = i - 1; j >= 0 && temp < arry[j]; j--)
{
arry[j + 1] = arry[j];
}
arry[j + 1] = temp;
}
}
}
測試
static void Main(string[] args)
{
int[] arry = new int[] { 34,1,221,50,44,58,12};
//arry.BubbleSort();
//arry.QuickSort(0, arry.Length-1 );
arry.InsertSort();
for (int i = 0; i < arry.Length; i++)
{
Console.Write("\t" + arry[i]);
}
Console.Read();
}
結果
希爾排序
希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因DL．Shell于1959年提出而得名。
希爾排序是基于插入排序的以下兩點性質而提出改進方法的：
插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率。
但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位。
基本思想
先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然后， 取第二個增量d2<d1重復上述的分組和排序，直至所取的增量 =1( < …<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。
該方法實質上是一種分組插入方法
比較相隔較遠距離（稱為增量）的數，使得數移動時能跨過多個元素，則進行一次比[2] 較就可能消除多個元素交換。D.L.shell于1959年在以他名字命名的排序算法中實現了這一思想。算法先將要排序的一組數按某個增量d分成若干組， 每組中記錄的下標相差d.對每組中全部元素進行排序，然后再用一個較小的增量對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數被分成一組， 排序完成。
一般的初次取序列的一半為增量，以后每次減半，直到增量為1。
代碼實現
/// <summary>
/// 希爾排序
/// </summary>
/// <param name="arry">待排序的數組</param>
public static void ShellSort(this int[] arry)
{
int length = arry.Length;
for (int h = length / 2; h > 0; h = h / 2)
{
//here is insert sort
for (int i = h; i < length; i++)
{
int temp = arry[i];
if (temp < arry[i - h])
{
for (int j = 0; j < i; j += h)
{
if (temp<arry[j])
{
temp = arry[j];
arry[j] = arry[i];
arry[i] = temp;
}
}
}
}
}
}
測試
static void Main(string[] args)
{
int[] arry = new int[] { 34,1,221,50,44,58,12};
//arry.BubbleSort();
//arry.QuickSort(0, arry.Length-1 );
//arry.InsertSort();
arry.ShellSort();
for (int i = 0; i < arry.Length; i++)
{
Console.Write("\t" + arry[i]);
}
Console.Read();
}
結果
選擇排序
簡單選擇排序
設所排序序列的記錄個數為n。i取1,2,…,n-1,從所有n-i+1個記錄（Ri,Ri+1,…,Rn）中找出排序碼最小的記錄，與第i個記錄交換。執行n-1趟 后就完成了記錄序列的排序。
在簡單選擇排序過程中，所需移動記錄的次數比較少。最好情況下，即待排序記錄初始狀態就已經是正序排列了，則不需要移動記錄。
最壞情況下，即待排序記錄初始狀態是按逆序排列的，則需要移動記錄的次數最多為3（n-1）。簡單選擇排序過程中需要進行的比較次數與初始狀態下待排序的 記錄序列的排列情況無關。當i=1時，需進行n-1次比較；當i=2時，需進行n-2次比較；依次類推，共需要進行的比較次數是(n-1)+(n- 2)+…+2+1=n(n-1)/2，即進行比較操作的時間復雜度為O(n^2)，進行移動操作的時間復雜度為O(n)。
代碼實現
/// <summary>
/// 簡單選擇排序
/// </summary>
/// <param name="arry">待排序的數組</param>
public static void SimpleSelectSort(this int[] arry)
{
int tmp = 0;
int t = 0;//最小數標記
for (int i = 0; i < arry.Length; i++)
{
t = i;
for (int j = i + 1; j < arry.Length; j++)
{
if (arry[t] > arry[j])
{
t = j;
}
}
tmp = arry[i];
arry[i] = arry[t];
arry[t] = tmp;
}
}
測試
static void Main(string[] args)
{
int[] arry = new int[] { 34,1,221,50,44,58,12};
//arry.BubbleSort();
//arry.QuickSort(0, arry.Length-1 );
//arry.InsertSort();
//arry.ShellSort();
arry.SimpleSelectSort();
for (int i = 0; i < arry.Length; i++)
{
Console.Write("\t" + arry[i]);
}
Console.Read();
}
結果
堆排序
堆排序(Heapsort)是指利用堆積樹（堆）這種數據結構所設計的一種排序算法，它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元 素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節點的值都不大于其父節點的值，即A[PARENT[i]] >= A[i]。在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。
代碼實現
/// <summary>
/// 堆排序
/// </summary>
/// <param name="arry"></param>
public static void HeapSort(this int[] arry, int top)
{
List<int> topNode = new List<int>();
for (int i = arry.Length / 2 - 1; i >= 0; i--)
{
HeapAdjust(arry, i, arry.Length);
}
for (int i = arry.Length - 1; i >= arry.Length - top; i--)
{
int temp = arry[0];
arry[0] = arry[i];
arry[i] = temp;
HeapAdjust(arry, 0, i);
}
}
/// <summary>
/// 構建堆
/// </summary>
/// <param name="arry"></param>
/// <param name="parent"></param>
/// <param name="length"></param>
private static void HeapAdjust(int[] arry, int parent, int length)
{
int temp = arry[parent];
int child = 2 * parent + 1;
while (child < length)
{
if (child + 1 < length && arry[child] < arry[child + 1]) child++;
if (temp >= arry[child])
break;
arry[parent] = arry[child];
parent = child;
child = 2 * parent + 1;
}
arry[parent] = temp;
}
測試
static void Main(string[] args)
{
int[] arry = new int[] { 34,1,221,50,44,58,12};
//arry.BubbleSort();
//arry.QuickSort(0, arry.Length-1 );
//arry.InsertSort();
//arry.ShellSort();
//arry.SimpleSelectSort();
arry.HeapSort(arry.Length);
for (int i = 0; i < arry.Length; i++)
{
Console.Write("\t" + arry[i]);
}
Console.Read();
}
結果
歸并排序
歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一 個有序表，稱為二路歸并。
歸并過程為：比較a[i]和a[j]的大小，若a[i]≤a[j]，則將第一個有序表中的元素a[i]復制到r[k]中，并令i和k分別加上1；否則將第 二個有序表中的元素a[j]復制到r[k]中，并令j和k分別加上1，如此循環下去，直到其中一個有序表取完，然后再將另一個有序表中剩余的元素復制到r 中從下標k到下標t的單元。歸并排序的算法我們通常用遞歸實現，先把待排序區間[s,t]以中點二分，接著把左邊子區間排序，再把右邊子區間排序，最后把 左區間和右區間用一次歸并操作合并成有序的區間[s,t]。
歸并操作(merge)，也叫歸并算法，指的是將兩個順序序列合并成一個順序序列的方法。
如 設有數列{6，202，100，301，38，8，1}
初始狀態：6,202,100,301,38,8，1
第一次歸并后：{6,202},{100,301},{8,38},{1}，比較次數：3；
第二次歸并后：{6,100,202,301}，{1,8,38}，比較次數：4；
第三次歸并后：{1,6,8,38,100,202,301},比較次數：4；
總的比較次數為：3+4+4=11,；
逆序數為14；
歸并操作的工作原理如下：
第一步：申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列
第二步：設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
第三步：比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
重復步驟3直到某一指針超出序列尾
將另一序列剩下的所有元素直接復制到合并序列尾
代碼實現
/// <summary>
/// 歸并排序
/// </summary>
/// <param name="arry"></param>
/// <param name="first"></param>
/// <param name="last"></param>
public static void MergeSort(this int[] arry, int first, int last)
{
if (first + 1 < last)
{
int mid = (first + last) / 2;
MergeSort(arry, first, mid);
MergeSort(arry, mid, last);
Merger(arry, first, mid, last);
}
}
/// <summary>
/// 歸并
/// </summary>
/// <param name="arry"></param>
/// <param name="first"></param>
/// <param name="mid"></param>
/// <param name="last"></param>
private static void Merger(int[] arry, int first, int mid, int last)
{
Queue<int> tempV = new Queue<int>();
int indexA, indexB;
//設置indexA，并掃描subArray1 [first,mid]
//設置indexB,并掃描subArray2 [mid,last]
indexA = first;
indexB = mid;
//在沒有比較完兩個子標的情況下，比較 v[indexA]和v[indexB]
//將其中小的放到臨時變量tempV中
while (indexA < mid && indexB < last)
{
if (arry[indexA] < arry[indexB])
{
tempV.Enqueue(arry[indexA]);
indexA++;
}
else
{
tempV.Enqueue(arry[indexB]);
indexB++;
}
}
//復制沒有比較完子表中的元素
while (indexA < mid)
{
tempV.Enqueue(arry[indexA]);
indexA++;
}
while (indexB < last)
{
tempV.Enqueue(arry[indexB]);
indexB++;
}
int index = 0;
while (tempV.Count > 0)
{
arry[first + index] = tempV.Dequeue();
index++;
}
}
測試
static void Main(string[] args)
{
int[] arry = new int[] { 34,1,221,50,44,58,12};
//arry.BubbleSort();
//arry.QuickSort(0, arry.Length-1 );
//arry.InsertSort();
//arry.ShellSort();
//arry.SimpleSelectSort();
//arry.HeapSort(arry.Length);
arry.MergeSort(0, arry.Length);
for (int i = 0; i < arry.Length; i++)
{
Console.Write("\t" + arry[i]);
}
Console.Read();
}
結果
基數排序
基數排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達到排序的作用，基數排序法是屬于穩定性的排序，其時間復雜度為O (nlog(r)m)，其中r為所采取的基數，而m為堆數，在某些時候，基數排序法的效率高于其它的穩定性排序法。
代碼實現
/// <summary>
/// 基數排序
/// 約定:待排數字中沒有0,如果某桶內數字為0則表示該桶未被使用,輸出時跳過即可
/// </summary>
/// <param name="arry">待排數組</param>
/// <param name="array_x">桶數組第一維長度</param>
/// <param name="array_y">桶數組第二維長度</param>
public static void RadixSort(this int[] arry, int array_x = 10, int array_y = 100)
{
/* 最大數字不超過999999999...(array_x個9) */
for (int i = 0; i < array_x; i++)
{
int[,] bucket = new int[array_x, array_y];
foreach (var item in arry)
{
int temp = (item / (int)Math.Pow(10, i)) % 10;
for (int l = 0; l < array_y; l++)
{
if (bucket[temp, l] == 0)
{
bucket[temp, l] = item;
break;
}
}
}
for (int o = 0, x = 0; x < array_x; x++)
{
for (int y = 0; y < array_y; y++)
{
if (bucket[x, y] == 0) continue;
arry[o++] = bucket[x, y];
}
}
}
}
測試
static void Main(string[] args)
{
int[] arry = new int[] { 34,1,221,50,44,58,12};
//arry.BubbleSort();
//arry.QuickSort(0, arry.Length-1 );
//arry.InsertSort();
//arry.ShellSort();
//arry.SimpleSelectSort();
//arry.HeapSort(arry.Length);
//arry.MergeSort(0, arry.Length);
arry.RadixSort();
for (int i = 0; i < arry.Length; i++)
{
Console.Write("\t" + arry[i]);
}
Console.Read();
}
結果
總結
整數數組各種排序算法擴展類
/// <summary>
/// 排序輔助類
/// </summary>
public static class SortExtention
{
/// <summary>
/// 冒泡排序
/// </summary>
/// <param name="arry">要排序的整數數組</param>
public static void BubbleSort(this int[] arry)
{
for (int i = 0; i < arry.Length; i++)
{
for (int j = 0; j < arry.Length - 1 - i; j++)
{
//比較相鄰的兩個元素，如果前面的比后面的大，則交換位置
if (arry[j] > arry[j + 1])
{
int temp = arry[j + 1];
arry[j + 1] = arry[j];
arry[j] = temp;
}
}
}
}
/// <summary>
/// 快速排序
/// </summary>
/// <param name="arry">要排序的數組</param>
/// <param name="left">低位</param>
/// <param name="right">高位</param>
public static void QuickSort(this int[] arry, int left, int right)
{
//左邊索引小于右邊，則還未排序完成
if (left < right)
{
//取中間的元素作為比較基準，小于他的往左邊移，大于他的往右邊移
int middle = arry[(left + right) / 2];
int i = left - 1;
int j = right + 1;
while (true)
{
//移動下標，左邊的往右移動，右邊的向左移動
while (arry[++i] < middle && i < right) ;
while (arry[--j] > middle && j > 0) ;
if (i >= j)
break;
//交換位置
int number = arry[i];
arry[i] = arry[j];
arry[j] = number;
}
QuickSort(arry, left, i - 1);
QuickSort(arry, j + 1, right);
}
}
/// <summary>
/// 直接插入排序
/// </summary>
/// <param name="arry">要排序的數組</param>
public static void InsertSort(this int[] arry)
{
//直接插入排序是將待比較的數值與它的前一個數值進行比較，所以外層循環是從第二個數值開始的
for (int i = 1; i < arry.Length; i++)
{
//如果當前元素小于其前面的元素
if (arry[i] < arry[i - 1])
{
//用一個變量來保存當前待比較的數值，因為當一趟比較完成時，我們要將待比較數值置入比它小的數值的后一位
int temp = arry[i];
int j = 0;
for (j = i - 1; j >= 0 && temp < arry[j]; j--)
{
arry[j + 1] = arry[j];
}
arry[j + 1] = temp;
}
}
}
/// <summary>
/// 希爾排序
/// </summary>
/// <param name="arry">待排序的數組</param>
public static void ShellSort(this int[] arry)
{
int length = arry.Length;
for (int h = length / 2; h > 0; h = h / 2)
{
//here is insert sort
for (int i = h; i < length; i++)
{
int temp = arry[i];
if (temp < arry[i - h])
{
for (int j = 0; j < i; j += h)
{
if (temp < arry[j])
{
temp = arry[j];
arry[j] = arry[i];
arry[i] = temp;
}
}
}
}
}
}
/// <summary>
/// 簡單選擇排序
/// </summary>
/// <param name="arry">待排序的數組</param>
public static void SimpleSelectSort(this int[] arry)
{
int tmp = 0;
int t = 0;//最小數標記
for (int i = 0; i < arry.Length; i++)
{
t = i;
for (int j = i + 1; j < arry.Length; j++)
{
if (arry[t] > arry[j])
{
t = j;
}
}
tmp = arry[i];
arry[i] = arry[t];
arry[t] = tmp;
}
}
/// <summary>
/// 堆排序
/// </summary>
/// <param name="arry"></param>
public static void HeapSort(this int[] arry, int top)
{
List<int> topNode = new List<int>();
for (int i = arry.Length / 2 - 1; i >= 0; i--)
{
HeapAdjust(arry, i, arry.Length);
}
for (int i = arry.Length - 1; i >= arry.Length - top; i--)
{
int temp = arry[0];
arry[0] = arry[i];
arry[i] = temp;
HeapAdjust(arry, 0, i);
}
}
/// <summary>
/// 構建堆
/// </summary>
/// <param name="arry"></param>
/// <param name="parent"></param>
/// <param name="length"></param>
private static void HeapAdjust(int[] arry, int parent, int length)
{
int temp = arry[parent];
int child = 2 * parent + 1;
while (child < length)
{
if (child + 1 < length && arry[child] < arry[child + 1]) child++;
if (temp >= arry[child])
break;
arry[parent] = arry[child];
parent = child;
child = 2 * parent + 1;
}
arry[parent] = temp;
}
/// <summary>
/// 歸并排序
/// </summary>
/// <param name="arry"></param>
/// <param name="first"></param>
/// <param name="last"></param>
public static void MergeSort(this int[] arry, int first, int last)
{
if (first + 1 < last)
{
int mid = (first + last) / 2;
MergeSort(arry, first, mid);
MergeSort(arry, mid, last);
Merger(arry, first, mid, last);
}
}
/// <summary>
/// 歸并
/// </summary>
/// <param name="arry"></param>
/// <param name="first"></param>
/// <param name="mid"></param>
/// <param name="last"></param>
private static void Merger(int[] arry, int first, int mid, int last)
{
Queue<int> tempV = new Queue<int>();
int indexA, indexB;
//設置indexA，并掃描subArray1 [first,mid]
//設置indexB,并掃描subArray2 [mid,last]
indexA = first;
indexB = mid;
//在沒有比較完兩個子標的情況下，比較 v[indexA]和v[indexB]
//將其中小的放到臨時變量tempV中
while (indexA < mid && indexB < last)
{
if (arry[indexA] < arry[indexB])
{
tempV.Enqueue(arry[indexA]);
indexA++;
}
else
{
tempV.Enqueue(arry[indexB]);
indexB++;
}
}
//復制沒有比較完子表中的元素
while (indexA < mid)
{
tempV.Enqueue(arry[indexA]);
indexA++;
}
while (indexB < last)
{
tempV.Enqueue(arry[indexB]);
indexB++;
}
int index = 0;
while (tempV.Count > 0)
{
arry[first + index] = tempV.Dequeue();
index++;
}
}
/// <summary>
/// 基數排序
/// 約定:待排數字中沒有0,如果某桶內數字為0則表示該桶未被使用,輸出時跳過即可
/// </summary>
/// <param name="arry">待排數組</param>
/// <param name="array_x">桶數組第一維長度</param>
/// <param name="array_y">桶數組第二維長度</param>
public static void RadixSort(this int[] arry, int array_x = 10, int array_y = 100)
{
/* 最大數字不超過999999999...(array_x個9) */
for (int i = 0; i < array_x; i++)
{
int[,] bucket = new int[array_x, array_y];
foreach (var item in arry)
{
int temp = (item / (int)Math.Pow(10, i)) % 10;
for (int l = 0; l < array_y; l++)
{
if (bucket[temp, l] == 0)
{
bucket[temp, l] = item;
break;
}
}
}
for (int o = 0, x = 0; x < array_x; x++)
{
for (int y = 0; y < array_y; y++)
{
if (bucket[x, y] == 0) continue;
arry[o++] = bucket[x, y];
}
}
}
}
}
SortExtention
各排序算法時間復雜度與空間復雜度
來源：wolfy的博客