四種簡單的排序算法
我覺得如果想成為一名優秀的開發者，不僅要積極學習時下流行的新技術，比如WCF、Asp.Net MVC、AJAX等，熟練應用一些已經比較成熟的技術，比如Asp.Net、WinForm。還應該有着牢固的計算機基礎知識，比如資料結構、作業系統、編譯原理、網絡與資料通信等。有的朋友可能覺得這方面的東西過于艱深和理論化，望而卻步，但我覺得假日裡花上一個下午的時間，研究一種算法或者一種資料結構，然後寫寫心得，難道不是一件樂事麼？是以，我打算将一些常見的資料結構和算法總結一下，不一定要集中一段時間花費很大精力，隻是在比較空閑的時間用一種很放松的心态去完成。我最不願意的，就是将寫部落格或者是學習技術變為一項工作或者負擔，應該将它們視為生活中的一種消遣。人們總是說堅持不易，實際上當你提到“堅持”兩個字之時，說明你已經将這件事視為了一種痛苦，你的内心深處并不願意做這件事，是以才需要堅持。你從不曾聽人說“我堅持玩了十年的電子遊戲”，或者“堅持看了十年動漫、電影”、“堅持和心愛的女友相處了十年”吧？我從來不曾堅持，因為我将其視為一個愛好和消遣，就像許多人玩網絡遊戲一樣。
好了，閑話就說這麼多吧，我們回到正題。因為這方面的著作很多，是以這裡隻給出簡單的描述和實作，供我本人及感興趣的朋友參考。我會盡量用C#和C++兩種語言實作，對于一些不好用C#表達的結構，僅用C++實作。
本文将描述四種最簡單的排序方法，插入排序、泡沫排序、選擇排序、希爾排序，我在這裡将其稱為“簡單排序”，是因為它們相對于快速排序、歸并排序、堆排序、配置設定排序、基數排序從了解和算法上要簡單一些。對于後面這幾種排序，我将其稱為“進階排序”。
簡單排序
開始之前先聲明一個約定，對于數組中儲存的資料，統一稱為
記錄，以避免和“元素”，“對象”等名稱相混淆。對于一個記錄，用于排序的碼，稱為
關鍵碼。很顯然，關鍵碼的選擇與數組中記錄的類型密切相關，如果記錄為int值，則關鍵碼就是本身；如果記錄是自定義對象，它很可能包含了多個字段，那麼標明這些字段之一為關鍵碼。凡是有關排序和查找的算法，就會關系到兩個記錄比較大小，而如何決定兩個對象的大小，應該由算法程式的用戶端（客戶對象）決定。對于.NET來說，我們可以建立一個實作了IComparer<T>的類（對于C++也是類似）。關于IComparer<T>的更多資訊，可以參考這篇文章《
基于業務對象的排序》。最後，為了使程式簡單，對于數組為空的情況我并沒有做處理。
1.插入排序
算法思想
插入排序使用了兩層嵌套循環，逐個處理待排序的記錄。每個記錄與前面已經排好序的記錄序列進行比較，并将其插入到合适的位置。假設數組長度為n，外層循環控制變量i由1至n-1依次遞進，用于選擇目前處理哪條記錄；裡層循環控制變量j，初始值為i，并由i至1遞減，與上一記錄進行對比，決定将該元素插入到哪一個位置。這裡的關鍵思想是，
當處理第i條記錄時，前面i-1條記錄已經是有序的了。需要注意的是，因為是将目前記錄與相鄰的上一記錄相比較，是以循環控制變量的起始值為1（數組下标），如果為0的話，上一記錄為-1，則數組越界。
現在我們考察一下第i條記錄的處理情況：假設外層循環遞進到第i條記錄，設其關鍵碼的值為X，那麼此時有可能有兩種情況：
- 如果上一記錄比X大，那麼就交換它們，直到上一記錄的關鍵碼比X小或者相等為止。
- 如果上一記錄比X小或者相等，那麼之前的所有記錄一定是有序的，且都比X小，此時退出裡層循環。外層循環向前遞進，處理下一條記錄。
算法實作(C#)
public class SortAlgorithm {
// 插入排序
public static void InsertSort<T, C>(T[] array, C comparer)
where C:IComparer<T>
{
for (int i = 1; i <= array.Length - 1; i++) {
//Console.Write("{0}: ", i);
int j = i;
while (j>=1 && comparer.Compare(array[j], array[j - 1]) < 0) {
swap(ref array[j], ref array[j-1]);
j--;
}
//Console.WriteLine();
//AlgorithmHelper.PrintArray(array);
}
}
// 交換數組array中第i個元素和第j個元素
private static void swap<T>(ref T x,ref T y) {
// Console.Write("{0}<-->{1} ", x, y);
T temp = x;
x = y;
y = temp;
}
上面Console.WriteLine()方法和AlgorithmHelper.PrintArray()方法僅僅是出于測試友善，PrintArray()方法依次列印了數組的内容。swap<T>()方法則用于交換數組中的兩條記錄，也對交換數進行了列印（這裡我注釋掉了，但在測試時可以取消對它們的注釋）。外層for循環控制變量i表示目前處理第i條記錄。
public class AlgorithmHelper {
// 列印數組内容
public static void PrintArray<T>(T[] array) {
Console.Write(" Array:");
foreach (T item in array) {
Console.Write(" {0}", item);
}
Console.WriteLine();
// 獲得Comparer，進行比較
public class ComparerFactory {
public static IComparer<int> GetIntComparer() {
return new IntComparer();
public class IntComparer : IComparer<int> {
public int Compare(int x, int y) {
return x.CompareTo(y);
上面這段代碼我們建立了一個ComparerFactory類，它用于獲得一個IntComparer對象，這個對象實作了IComparer<T>接口，規定了兩個int類型的關鍵碼之間比較大小的規則。如果你有自定義的類型，比如叫MyType，隻需要在ComparerFactory中再添加一個類，比如叫MyTypeComparer，然後讓這個類也實作IComparer<T>接口，最後再添加一個方法傳回MyTypeComparer就可以了。
輸出示範(C#)
接下來我們看一下用戶端代碼和輸出：
static void Main(string[] args) {
int[] array = {42,20,17,13,28,14,23,15};
//int[] array = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
AlgorithmHelper.PrintArray(array);
SortAlgorithm.InsertSort
(array, ComparerFactory.GetIntComparer());
算法實作(C++)
// 對int類型進行排序
class IntComparer{
public:
static bool Smaller(int x, int y){
return x<y;
static bool Equal(int x, int y){
return x==y;
static bool Larger(int x, int y){
return x>y;
};
// 插入排序
template <class T, class C>
void InsertSort(T a[], int length){
for(int i=1;i<=length-1;i++){
int j = i;
while(j>=1 && C::Smaller(a[j], a[j-1])){
swap(a[j], a[j-1]);
j--;
2.冒泡排序
如果你從沒有學習過有關算法方面的知識，而需要設計一個數組排序的算法，那麼很有可能設計出的就是泡沫排序算法了。因為它很好了解，實作起來也很簡單。它也含有兩層循環，假設數組長度為n，外層循環控制變量i由0到n-2遞增，這個外層循環并不是處理某個記錄，隻是控制比較的趟數，由0到n-2，一共比較n-1趟。為什麼n個記錄隻需要比較n-1趟？我們可以先看下最簡單的兩個數排序：比如4和3，我們隻要比較一趟，就可以得出3、4。對于更多的記錄可以類推。
數組記錄的交換由裡層循環來完成，控制變量j初始值為n-1（數組下标），一直遞減到1。數組記錄從數組的末尾開始與相鄰的上一個記錄相比，如果上一記錄比目前記錄的關鍵碼大，則進行交換，直到目前記錄的下标為1為止（此時上一記錄的下标為0）。整個過程就好像一個氣泡從底部向上升，于是這個排序算法也就被命名為了冒泡排序。
我們來對它進行一個考察，按照這種排序方式，在進行完第一趟循環之後，最小的一定位于數組最頂部（下标為0）；第二趟循環之後，次小的記錄位于數組第二（下标為1）的位置；依次類推，第n-1趟循環之後，第n-1小的記錄位于數組第n-1（下标為n-2）的位置。此時無需再進行第n趟循環，因為最後一個已經位于數組末尾（下标為n-1）位置了。
// 泡沫排序
public static void BubbleSort<T, C>(T[] array, C comparer)
where C : IComparer<T>
{
int length = array.Length;
for (int i = 0; i <= length - 2; i++) {
//Console.Write("{0}: ", i + 1);
for (int j = length - 1; j >= 1; j--) {
if (comparer.Compare(array[j], array[j - 1]) < 0) {
swap(ref array[j], ref array[j - 1]);
//Console.WriteLine();
//AlgorithmHelper.PrintArray(array);
SortAlgorithm.BubbleSort
// 冒泡排序
void BubbleSort(T a[], int length){
for(int i=0;i<=length-2;i++){
for(int j=length-1; j>=1; j--){
if(C::Smaller(a[j], a[j-1]))
swap(a[j], a[j-1]);
3.選擇排序
選擇排序是對冒泡排序的一個改進，從上面冒泡排序的輸出可以看出，在第一趟時，為了将最小的值13由數組末尾冒泡的數組下标為0的第一個位置，進行了多次交換。對于後續的每一趟，都會進行類似的交換。
選擇排序的思路是：對于第一趟，搜尋整個數組，尋找出最小的，然後放置在數組的0号位置；對于第二趟，搜尋數組的n-1個記錄，尋找出最小的（對于整個數組來說則是次小的），然後放置到數組的第1号位置。在第i趟時，搜尋數組的n-i+1個記錄，尋找最小的記錄（對于整個數組來說則是第i小的），然後放在數組i-1的位置（注意數組以0起始）。可以看出，選擇排序顯著的減少了交換的次數。
需要注意的地方是：在第i趟時，内層循環并不需要遞減到1的位置，隻要循環到與i相同就可以了，因為之前的位置一定都比它小（也就是第i小）。另外裡層循環是j>i，而不是j>=i，這是因為i在進入循環之後就被立即儲存到了lowestIndex中。
public static void SelectionSort<T, C>(T[] array, C comparer)
Console.Write("{0}: ", i+1);
int lowestIndex = i; // 最小記錄的數組索引
for (int j = length - 1; j > i; j--) {
if (comparer.Compare(array[j], array[lowestIndex]) < 0)
lowestIndex = j;
swap(ref array[i], ref array[lowestIndex]);
AlgorithmHelper.PrintArray(array);
SortAlgorithm.SelectionSort
// 選擇排序
void SelectionSort(T a[], int length) {
for(int i = 0; i <= length-2; i++){
int lowestIndex = i;
for(int j = length-1; j>i; j--){
if(C::Smaller(a[j], a[lowestIndex]))
swap(a[i], a[lowestIndex]);
4.希爾排序
希爾排序利用了插入排序的一個特點來優化排序算法，插入排序的這個特點就是：
當數組基本有序的時候，插入排序的效率比較高。比如對于下面這樣一個數組：
int[] array = { 1, 0, 2, 3, 5, 4, 8, 6, 7, 9 };
插入排序的輸出如下：
可以看到，盡管比較的趟數沒有減少，但是交換的次數卻明顯很少。希爾排序的總體想法就是先讓數組基本
有序，最後再應用插入排序。具體過程如下：假設有數組int a[] = {42,20,17,13,28,14,23,15}，不失一般性，我們設其長度為length。
第一趟時，步長step = length/2 = 4，将數組分為4組，每組2個記錄，則下标分别為(0,4)(1,5)(2,6)(3,7)；轉換為數值，則為{42,28}, {20,14}, {17,23}, {13,15}。然後對每個分組進行插入排序，之後分組數值為{28,42}, {14,20}, {17,23}, {13,15}，而實際的原數組的值就變成了{28,14,17,13,42,20,23,15}。這裡要注意的是分組中記錄在原數組中的位置，以第2個分組{14,20}來說，它的下标是(1,5)，是以這兩個記錄在原數組的下标分别為a[1]=14;a[5]=20。
第二趟時，步長 step = step/2 = 2，将數組分為2組，每組4個記錄，則下标分别為(0,2,4,6)(1,3,5,7)；轉換為數值，則為{28,17,42,23}, {14,13,20,15}，然後對每個分組進行插入排序，得到{17,23,28,42}{13,14,15,20}。此時數組就成了{17,13,23,14,28,15,42,20}，已經基本有序。
第三趟時，步長 step=step/2 = 1，此時相當進行一次完整的插入排序，得到最終結果{13,14,15,17,20,23,28,42}。
// 希爾排序
public static void ShellSort<T, C>(T[] array, C comparer)
for (int i = array.Length / 2; i >= 1; i = i / 2) {
Console.Write("{0}: ", i);
for (int j = 0; j < i; j++) {
InsertSort(array, j, i, comparer);
// 用于希爾排序的插入排序
private static void InsertSort<T, C>
(T[] array, int startIndex, int step, C comparer)
for (int i = startIndex + step; i <= array.Length - 1; i += step) {
while(j>= step && comparer.Compare(array[j], array[j - step]) <0 ){
swap(ref array[j], ref array[j - step]);
j -= step;
注意這裡插入排序InsertSort()方法的參數，startIndex是分組的起始索引，step是步長，可以看出，
前面的插入排序隻是此處step=1,startindex=0的一個特例。
SortAlgorithm.ShellSort
template<class T, class C>
void ShellSort(T a[], int length){
for(int i = length/2; i >= 1; i = i/2 ){
for(int j = 0; j<i; j++){
InsertSort<T, C>(&a[j], length-1, i);
void InsertSort(T a[], int length, int step){
for(int i = step; i<length; i+= step){
while(j>=step && C::Smaller(a[j], a[j-step])){
swap(a[j], a[j-step]);
j-=step;
對于上面三種算法的代價，插入排序、冒泡排序、選擇排序，都是Θ(n2)，而希爾排序略好一些，是Θ（n1.5），關于算法分析，大家感興趣可以參考相關書籍。這裡推薦《
資料結構與算法分析(C++版)第二版》和《
算法I~IV（C++實作）——基礎、資料結構、排序和搜尋》，都很不錯，我主要也是參考這兩本書。
感謝閱讀，希望這篇文章可以給你帶來幫助。