從學第一門計算機語言開始就了解了選擇、冒泡排序等算法，後來又學習了高效的歸并、快速排序，排序算法種類很多，一直都想把它們總結一下，但卻信心不足。這幾天終于下定決心嘗試寫一寫，于是看了算法導論，在網上也查了很多資料，最終将這些排序算法一個一個用C語言實作，最後進行了測試。看着它們一個個運作起來心裡還是很有成就感的。接着用了兩天時間寫了下面這篇小文章，雖然寫下了，但對于很多問題比如一些算法複雜度的證明還是不太明白，估計代碼寫得也不夠好，待有了新的領悟再來補充。
文章中的排序算法有:1、選擇排序；2、插入排序；3、希爾排序；4、冒泡排序；5、快速排序；6、歸并排序；7，堆排序；8、計數排序；9、基數排序；10、桶排序。
一、選擇排序（Selection Sort）
1、算法思想
選擇排序是一種簡單直覺的排序算法，首先從數組中先找到最小的元素，放到第一個位置。然後從剩餘元素中找到最小的，放到第二個位置……以此類推，就可以完成整個的排序工作了。
2、算法實作
數組A中存放length個整數。
void SelectSort(int A[], int length) //選擇排序
{
int i, j, min,temp;
for (i = ; i < length - ; ++i)
{
min = i; //假設第i個元素是最小的元素
for (j = i + ; j < length; ++j)
if (A[j] < A[min]) //如果有比A[i]還小的元素,則記錄
min = j;
if (min != i) //如果最小元素不是A[i]，則交換
{
temp = A[min];
A[min] = A[i];
A[i] = temp;
}
}
}
3、算法分析
算法中含有雙重循環，容易得出時間複雜度也是O(n*n)。在n比較小時，算法可以保證一定的速度，當n足夠大時，算法的效率會降低，并且随着n的增大，算法的時間增長很快。最差時間複雜度О(n²)，最優時間複雜度О(n²)，平均時間複雜度О(n²)，最差空間複雜度О(n) 。
二、插入排序（Insertion Sort）
1、算法思想
插入排序的工作原理是通過建構有序序列，對于未排序資料，在已排序序列中從後向前掃描，找到相應位置并插入。插入排序在實作上，通常采用in-place排序（即隻需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反複把已排序元素逐漸向後挪位，為最新元素提供插入空間。
2、算法實作
void InsertSort(int A[], int length) //插入排序
{
if (length < ) //隻有一個元素，不用排序
return;
int i, j, key;
for ( j = ; j < length; j++) // 從第二個元素開始周遊
{
i = j - ; //j之前的元素都已經排好,i從j-1周遊
key = A[j];
while (i >= && A[i] > key) //如果A[i]比key大，則将A[i]後移一個元素
{
A[i + ] = A[i];
i--;
}
A[i + ] = key; //找到位置，複制key
}
}
3、 算法分析
如果目标是把n個元素的序列升序排列，那麼采用插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需(n-1)次即可。最壞情況就是，序列是降序排列，那麼此時需要進行的比較共有n(n-1)/2次。插入排序的指派操作是比較操作的次數減去(n-1)次。平均來說插入排序算法複雜度為O(n*n)。因而，插入排序不适合對于資料量比較大的排序應用。但是，如果需要排序的資料量很小，例如，量級小于千，那麼插入排序還是一個不錯的選擇。
三、希爾排序（Shell Sort）
1、算法思想
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。希爾排序是非穩定排序算法。希爾排序是基于插入排序的以下兩點性質而提出改進方法的：
(1)插入排序在對幾乎已經排好序的資料操作時，效率高，即可以達到線性排序的效率
(2)但插入排序一般來說是低效的，因為插入排序每次隻能将資料移動一位
希爾排序基本思想：先取一個小于length的整數gap作為第一個步長把全部資料分成gap個組。所有距離為gap的倍數的資料放在同一個組中。首先在各組内進行插入排序；然後，取得第二個步長重複上述的分組和排序，直至所取的步長gap=1，即所有資料放在同一組中進行插入排序為止。一般步長選擇為\frac{n}{2}并且對步長取半直到步長達到1。
2、算法實作
void ShellSort(int A[], int length) //希爾排序
{
int i, j, gap,key;
for ( gap = length/; gap > ; gap /= )
for ( j = gap; j < length; j++)
{
i = j - gap;
key = A[j];
while (A[i] > key && i>=)
{
A[i + gap] = A[i];
i = i - gap;
}
A[i + gap] = key;
}
}
3、算法分析
希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，是以插入排序的元素個數很少，速度很快；當元素基本有序了，步長很小，插入排序對于有序的序列效率很高，是以，希爾排序的時間複雜度會比o(n^2)好一些。希爾排序的時間複雜度與步長序列的選取有關，例如取希爾步長的時間複雜度為O(n^2)，而Hibbard步長的時間複雜度為O( n^1.5 )，下界是n*log2n，平均時間複雜度為O(n^1.3)，在最壞的情況下和平均情況下執行效率相差不是很多。
四、冒泡排序(Bubble Sort)
1、算法思想
冒泡排序需要周遊要排序的數組，一次比較兩個元素，如果順序錯誤就把它們交換過來。重複地周遊直到沒有再需要交換，排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數組的頂端。
2、算法實作
void BubbleSort(int A[], int length) //冒泡排序
{
int i, j,t;
for (j = ;j <length-;j++)
for (i = ;i < length - j - ;i++)
if (A[i + ] < A[i])
{
t = A[i + ];
A[i + ] = A[i];
A[i] = t;
}
}
3、算法分析
冒泡排序與插入排序擁有相等的運作時間，但是需要的交換次數卻不同。在最壞的情況下，冒泡排序需要O(n^2)次交換，而插入排序最多需要O(n)次交換，是以冒泡排序效率很低。
五、快速排序（Quick Sort）
快速排序算法由C. A. R. Hoare在1962年提出。
1、算法思想
快速排序采用分治政策把一個數組分為兩個子數組。
步驟為：
（1）從數組中挑出一個元素，稱為”基準”（pivot），所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區結束之後，該基準就處于數組的中某一位置。這個稱為分區（partition）操作。
（2）通過遞歸調用快速排序，對子數組排序。
（3）因為子數組都是原址排序的，不需要合并，數組已經有序。
2、算法實作
（1）快速排序算法
void QuickSort(int A[], int left, int right) //快速排序
{
int mid;
if (left < right)
{
mid = Partition(A, left, right);
QuickSort(A, left, mid - );
QuickSort(A, mid + , right);
}
}
（2）劃分算法
int Partition(int A[], int p, int r) //對數組A[left..right]原址重排
{
int key = A[r];
int i = p - ;
int j,temp;
for (j = p;j < r;j++)
{
if (A[j] <= key)
{
i++;
temp = A[i];A[i] = A[j];A[j] = temp;
}
}
temp = A[i+];A[i+] = A[r];A[r] = temp;
return i + ;
}
劃分算法圖示:
令key = A[r]，淺陰影部分數組元素劃在第一部分，其值都不大于key，深陰影部分數組元素劃在第二部分，其值都大于key，無陰影則不屬于任何部分。
（a）初始化；
（b）2與它自身交換；
（c）~（d）8和7被添加到較大部分;
（e）1和8交換，數值較小部分規模增加；
（g）~（h）5和6被包含進較大部分，循環結束;
（i）交換key使其位于中間。
3、算法分析
快速排序的時間主要耗費在劃分操作上，對長度為 n的區間進行劃分，共需 n-1 次關鍵字的比較。
最壞時間複雜度
最壞情況是每次劃分選取的基準都是目前無序區中關鍵字最小(或最大)的資料，劃分的結果是基準左邊的子區間為空(或右邊的子區間為空)，而劃分所得的另一個非空的子區間中記錄數目，僅僅比劃分前的無序區中記錄個數減少一個。 是以，快速排序必須做 n-1 次劃分，第i次劃分開始時區間長度為 n-i+1，所需的比較次數為 n-i(1≤i≤n-1)，故總的比較次數達到最大值：Cmax = n(n-1)/2=O(n^2)
最好時間複雜度
在最好情況下，每次劃分所取的基準都是目前無序區的”中值”資料，劃分的結果是基準的左、右兩個無序子區間的長度大緻相等。總的關鍵字比較次數：O(nlgn)。盡管快速排序的最壞時間為 O(n^2)，但就平均性能而言，它是基于關鍵字比較的内部排序算法中速度最快者，快速排序亦是以而得名。它的平均時間複雜度為 O(nlgn)。
空間複雜度
快速排序在系統内部需要一個棧來實作遞歸。若每次劃分較為均勻，則其遞歸樹的高度為 O(lgn)，故遞歸後需棧空間為 O(lgn)。最壞情況下，遞歸樹的高度為 O(n)，所需的棧空間為 O(n)。
六、歸并排序(Merge Sort)
歸并排序是建立在歸并操作上的一種有效的排序算法，效率為O(n log n)。1945年由約翰·馮·諾伊曼首次提出。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞歸可以同時進行。
1、算法思想
分治模式:
分解：分解待排序的n個元素組成的序列成各具有n/2個元素的兩個子序列;
解決：使用歸并排序遞歸地排序兩個子序列;
合并：合并兩個已經排序好的子序列，産生已排序的序列。
2、算法實作
合并子數組不難，有很多種算法，可以使用數組或者指針。下面給出使用數組的方法：首先定義一個與待排序數組A同樣大小的數組temp,從前往後依次比較兩個子數組中的資料，将值小的存入temp數組中，然後再進行比較，如果其中一個子數組為空，那麼直接将另一個子數組的資料依次取出放到temp後即可。
void Merge(int A[], int first, int mid, int last) //合并子數組
{
int temp[MAXSIZE]; //存儲排序後的數組
int i = first, j = mid + ;
int k = ; //temp數組下标
while (i <= mid && j <= last) //分别從第一個元素比較兩個子數組，
{ //将小的存儲到temp數組中
if (A[i] <= A[j])
temp[k++] = A[i++];
else
temp[k++] = A[j++];
}
while(i <= mid) //如果第一個數組中還有元素，将其複制到temp數組後面
temp[k++] = A[i++];
while(j <= last) //如果第一個數組中還有元素，将其複制到temp數組後面
temp[k++] = A[j++];
for (i = ;i < k;i++) //最後将排序好的數組temp中的元素複制到A中
A[first + i] = temp[i];
}
歸并排序算法
void MergeSort(int A[], int first, int last) //歸并排序
{
if (first < last)
{
int mid = (first + last) / ;
MergeSort(A, first, mid);
MergeSort(A, mid + , last);
Merge(A, first, mid, last);
}
}
3、算法分析
比較操作的次數介于(nlgn)/2和nlgn - n + 1。 指派操作的次數是(2nlgn)。歸并算法的空間複雜度為：O(n)
最差時間複雜度 ：O(nlgn)
最優時間複雜度 ：O(n)
平均時間複雜度 ：O(nlgn)
七、堆排序（Heapsort）
1991年的計算機先驅獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德(Robert W．Floyd）和威廉姆斯(J．Williams）在1964年共同發明了著名的堆排序算法。
1、算法思想
堆排序是指利用堆這種資料結構所設計的一種排序算法。堆可以被看成是一個近似的完全二叉樹，并同時滿足堆的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。 若A[parent[i]] >= A[i]，則為最大堆；若A[parent[i]] <= A[i]，則為最小堆。
以二叉樹和數組形式展現的一個最大堆:
堆節點的通路
通常堆是通過一維數組來實作的。在數組起始位置為0的情形中：
父節點i的左子節點在位置(2*i+1);
父節點i的右子節點在位置(2*i+2);
子節點i的父節點在位置floor((i-1)/2);
堆的操作
在最大堆中，堆中的最大值總是位于根節點。定義以下幾種操作：
最大堆調整（MaxHeapify）：将堆的節點作調整，使得子節點永遠小于父節點，時間複雜度O(lgn)。
建立最大堆（BuildMaxHeap）：從無序的輸入數組中建立一個最大堆，具有線性時間複雜度。
堆排序（HeapSort）：對一個數組進行原址排序。
2、算法實作
(1)最大堆調整（MaxHeapify）
程式輸入為一個數組A和下标 i，假定根結點為LEFT( i )和RIGHT( i )的二叉樹都是最大堆，但這時A[ i ]可能小于其孩子，這就違背了最大堆得性質，MaxHeapify通過讓A[ i ]的值在最大堆中“逐級下降”，進而使得以下标為根結點的子樹重新遵循最大堆的性質。
void MaxHeapify(int A[],int length, int i) //維護堆的性質
{
int left = * i + ;
int right = * i + ;
int largest,temp;
if (left < length && A[left]>A[i])
largest = left;
else
largest = i;
if (right < length && A[right] > A[largest])
largest = right;
if (largest != i)
{
temp = A[largest];
A[largest] = A[i];
A[i] = temp;
MaxHeapify(A, length, largest);
}
}
(2)建立最大堆（BuildMaxHeap）
通過自底向上方法的方法利用MaxHeapify可以把一個大小為length的數組A轉換為最大堆。表面上看，每次調用MaxHeapify的時間複雜度是O(lgn)，BuildMaxHeap需要O(n)次這樣的調用，是以總的時間複雜度是O(nlgn)，但此結果不是漸進緊确的，可以證明，MaxHeapify的時間複雜度是O(n)，即線性時間。
void BuildMaxHeap(int A[], int length) //建堆;
{
int i;
for (i = (length - ) / ;i >= ;--i)
MaxHeapify(A, length, i);
}
(3)堆排序（HeapSort）
void HeapSort(int A[], int length) //堆排序算法
{
BuildMaxHeap(A, length);
int i, temp;
for (i = length - ;i > ;--i)
{
temp = A[];A[] = A[i];A[i] = temp;
length--;
MaxHeapify(A, length,);
}
}
首先利用BuildMaxHeap建立最大堆，A[0]就成了數組中最大的元素，然後将A[0]和最後一個元素A[length-1]交換，這樣，最大的元素就放到了正确的位置，但是新的堆(去掉最後一個元素後的)可能會違背最大堆得性質，于是調用MaxHeapify維護最大堆性質，接着重複操作直到堆中剩餘一個元素，排序完成。圖示如下:
3、算法分析
每次調用BuildMaxHeap的時間複雜度是O(n)，而n-1次調用MaxHeapify，每次時間複雜度是O(lgn)，是以堆排序過程HeapSort時間複雜度是O(nlgn)。
最差時間複雜度 O(nlgn)
最優時間複雜度 O(nlgn)
平均時間複雜度 O(nlgn)
最差空間複雜度 O(n) 。
八、計數排序（Counting Sort）
1、算法思想
計數排序是一種穩定的線性時間排序算法。計數排序假設n個輸入元素中的每一個都是在0~k區間内的一個整數，對每一個元素x，确定小于x的元素的個數，利用這一資訊，将x放到輸出數組的位置上。例如：如果有15個元素小于x，則x就應該放在第16個位置上。
2、算法實作
void CountingSort(int A[], int length) //計數排序
{
int i,j,k;
k=Max(A);
int C[k]; //在第x位置上存放小于x的元素的個數，k=Max(A);
int B[length]; //存放排序好的數列
for (i = ;i < k ;i++)
C[i] = ; //初始化，将C[]中元素全部置零
for (j = ;j < length;j++)
C[A[j]] = C[A[j]] + ; //C中第j個位置存A中元素j的個數
for (i = ;i < k;i++)
C[i] = C[i] + C[i - ]; //C中第j個位置存小于或等于元素j的個數
for (j = length - ;j >= ;j--) //排序，在B中，元素被放到正确的位置上
{
B[C[A[j]]-] = A[j];
C[A[j]] = C[A[j]] - ;
}
for (i = ;i < length - ;i++) //最後，将排序好的B中元素複制到A中
A[i] = B[i];
}
通俗地了解，例如有10個年齡不同的人，統計出有8個人的年齡比A小，那A的年齡就排在第9位，用這個方法可以得到其他每個人的位置，也就排好了序。當然，年齡有重複時需要特殊處理（保證穩定性），這就是為什麼最後要逆向填充目标數組，以及将每個元素的統計減去1的原因。算法的步驟圖示:
3、算法分析
當輸入的元素是n個0到k之間的整數時，它的運作時間是Θ(n + k)。計數排序不是比較排序，排序的速度快于任何比較排序算法。
* 九、基數排序（Radix Sort） *
1、算法思想
基數排序是一種非比較型整數排序算法，其原理是将整數按位數切割成不同的數字，然後按每個位數分别比較。由于整數也可以表達字元串（比如名字或日期）和特定格式的浮點數，是以基數排序也不是隻能使用于整數。基數排序的發明可以追溯到1887年赫爾曼·何樂禮在打孔卡片制表機（Tabulation Machine）上的貢獻。
2、算法實作
将所有待比較數值（正整數）統一為同樣的數位長度d，數位較短的數前面補零。然後，從最低位1開始，依次進行一次排序。這樣從最低位排序一直到最高位d排序完成以後，數列就變成一個有序序列。
RadixSort(A,d)
{
for(i= to d)
用一個穩定的算法對第i位排序;
}
3、算法分析
給定n個d位數，其中每一個數位有k個可能的取值。如果Radix使用的穩定排序算法耗時O(n+k)，那麼它就可以在O(d(n+k))時間内将這些數排好。
十、桶排序（Bucket Sort）
1、算法思想
桶排序将元素區間(a，b)劃分為若幹區間(或稱為桶)，然後對每個桶再分别排序（有可能再使用别的排序算法或是以遞歸方式繼續使用桶排序進行排序）。
算法步驟：
(1)設定一個數組當作空桶。
(2)周遊數組，并且把元素放到對應的桶(可用連結清單表示)中去。
(3)對每個不是空的桶進行排序。
(4)從不是空的桶裡把元素再放回原來的序列中。
舉例如下:假設A中共n個元素，數值在(0,1)區間内，數組B存放桶(連結清單)，周遊A，将A中元素A[i]放到B中第n*A[i]個桶中，接着将每個桶排序，最後将B中元素有序存到A中，排序完成。
2、算法實作
不用連結清單的一種實作方式如下:
void BucketSort(int A[], int length) //桶排序
{
int i, k=Max(A);
int B[k]; //定義桶，大小等于元素最大值
for (i = ;i < k - ;++i)
B[i] = ; //初始化桶
for (i = ;i < length;i++)
B[A[i]]++; //周遊A中元素，在桶中相應位置做标記(元素個數)
int j = ;
for (i = ;i < k - ;i++) //順序讀入到A中
while (B[i]-- > )
A[j++] = i;
}
3、算法分析
桶排序假設輸入資料服從均勻分布，它不是比較排序，不受O(nlgn)下限的影響，平均情況下時間代價為O(n)。
十一、算法性能比較
1、性能分析
(1).O(n^2)性能分析
平均性能為O(n^2)的有：插入排序，選擇排序，冒泡排序
在資料規模較小時(9W内)，差别不大。當資料規模較大時，冒泡排序算法的時間代價最高。
(2).O(nlogn)性能分析
平均性能為O(nlogn)的有：快速排序，歸并排序，希爾排序，堆排序。其中，快排是最好的， 其次是歸并和希爾，堆排序在資料量很大時效果明顯。這四種排序可看作為“先進算法”，其中，快速排序效率最高，但在待排序列基本有序的情況下，會變成冒泡排序，接近O(n^2)。
在排序的最終結果中，如果各元素的次序依賴它們之間的比較，這類算法就稱為比較算法，插入排序、冒泡排序、快速排序、堆排序等都是比較排序算法，由決策樹模型可得比較排序算法的下界是O(nlgn)。而計數排序、基數排序和桶排序不是比較排序，不受下界的限制