1.簡介
插入排序（Insertion Sort）的算法描述是一種簡單直觀的排序算法状飞。它的工作原理是通過構(gòu)建有序序列书斜，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描荐吉，找到相應(yīng)位置并插入焙糟。插入排序在實(shí)現(xiàn)上样屠，通常采用in-place排序（即只需用到O(1)的額外空間的排序）穿撮，因而在從后向前掃描過程中痪欲，需要反復(fù)把已排序元素逐步向后挪位悦穿，為最新元素提供插入空間。
2.算法描述
一般來說业踢，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：
1.從第一個(gè)元素開始知举，該元素可以認(rèn)為已經(jīng)被排序
2.取出下一個(gè)元素瞬沦，在已經(jīng)排序的元素序列中從后向前掃描
3.如果該元素（已排序）大于新元素，將該元素移到下一位置
4.重復(fù)步驟3逛钻，直到找到已排序的元素小于或者等于新元素的位置
5.將新元素插入到該位置后
6.重復(fù)步驟2~5
如果比較操作的代價(jià)比交換操作大的話僚焦，可以采用二分查找法來減少比較操作的數(shù)目绣的。該算法可以認(rèn)為是插入排序的一個(gè)變種叠赐，稱為二分查找排序屡江。
4.C#實(shí)現(xiàn)

/// <summary>
/// 插入排序
/// </summary>
public void InsertSort(int[] list)
{
for (int i = 1; i < list.Length; ++i)
{
int t = list[i];
int j = i;
while ((j > 0) && (list[j - 1] > t))
{
list[j] = list[j - 1];
--j;
}
list[j] = t;
}
}

二 希爾排序
1.簡介
希爾排序，也稱遞減增量排序算法惩嘉，是插入排序的一種更高效的改進(jìn)版本罢洲。希爾排序是非穩(wěn)定排序算法文黎。
2.算法實(shí)現(xiàn)
原始的算法實(shí)現(xiàn)在最壞的情況下需要進(jìn)行O(n2)的比較和交換惹苗。V. Pratt的書[1] 對(duì)算法進(jìn)行了少量修改耸峭，可以使得性能提升至O(n log2 n)。這比最好的比較算法的O(n log n)要差一些劳闹。
希爾排序通過將比較的全部元素分為幾個(gè)區(qū)域來提升插入排序的性能院究。這樣可以讓一個(gè)元素可以一次性地朝最終位置前進(jìn)一大步本涕。然后算法再取越來越小的步長進(jìn)行排序，算法的最后一步就是普通的插入排序菩颖，但是到了這步样漆，需排序的數(shù)據(jù)幾乎是已排好的了（此時(shí)插入排序較快）晦闰。
假設(shè)有一個(gè)很小的數(shù)據(jù)在一個(gè)已按升序排好序的數(shù)組的末端。如果用復(fù)雜度為O(n2)的排序（冒泡排序或插入排序）呻右，可能會(huì)進(jìn)行n次的比較和交換才能將該數(shù)據(jù)移至正確位置舞竿。而希爾排序會(huì)用較大的步長移動(dòng)數(shù)據(jù)窿冯，所以小數(shù)據(jù)只需進(jìn)行少數(shù)比較和交換即可到正確位置。
一個(gè)更好理解的希爾排序?qū)崿F(xiàn)：將數(shù)組列在一個(gè)表中并對(duì)列排序（用插入排序）。重復(fù)這過程执桌，不過每次用更長的列來進(jìn)行。最后整個(gè)表就只有一列了仰挣。將數(shù)組轉(zhuǎn)換至表是為了更好地理解這算法伴逸，算法本身僅僅對(duì)原數(shù)組進(jìn)行排序（通過增加索引的步長膘壶，例如是用i += step_size而不是i++）。

4.C#實(shí)現(xiàn)

/// <summary>
/// 希爾排序
/// </summary>
public void ShellSorter(int[] list)
{
int inc;
for (inc = 1; inc <= list.Length / 9; inc = 3 * inc + 1) ;
for (; inc > 0; inc /= 3)
{
for (int i = inc + 1; i <= list.Length; i += inc)
{
int t = list[i - 1];
int j = i;
while ((j > inc) && (list[j - inc - 1] > t))
{
list[j - 1] = list[j - inc - 1];
j -= inc;
}
list[j - 1] = t;
}
}
}

三 選擇排序

1.簡介
選擇排序(Selection sort)是一種簡單直觀的排序算法颓芭。它的工作原理如下顷锰。首先在未排序序列中找到最型鑫省（大）元素，存放到排序序列的起始位置州藕，然后束世，再從剩余未排序元素中繼續(xù)尋找最写膊！（大）元素毁涉，然后放到已排序序列的末尾锈死。以此類推，直到所有元素均排序完畢馅精。
選擇排序的主要優(yōu)點(diǎn)與數(shù)據(jù)移動(dòng)有關(guān)。如果某個(gè)元素位于正確的最終位置上粱檀，則它不會(huì)被移動(dòng)洲敢。選擇排序每次交換一對(duì)元素茄蚯，它們當(dāng)中至少有一個(gè)將被移到其最終位置上，因此對(duì)n個(gè)元素的表進(jìn)行排序總共進(jìn)行至多n-1次交換渗常。在所有的完全依靠交換去移動(dòng)元素的排序方法中壮不，選擇排序?qū)儆诜浅：玫囊环N皱碘。

4.C#實(shí)現(xiàn)

/// <summary>
/// 選擇排序
/// </summary>
private int min;
// private int m=0;
public void SelectionSorter(int[] list)
{
for (int i = 0; i < list.Length - 1; ++i)
{
min = i;
for (int j = i + 1; j < list.Length; ++j)
{
if (list[j] < list[min])
min = j;
}
int t = list[min];
list[min] = list[i];
list[i] = t;
}
}

四 冒泡排序

1.簡介
冒泡排序（Bubble Sort，臺(tái)灣譯為：泡沫排序或氣泡排序）是一種簡單的排序算法。它重復(fù)地走訪過要排序的數(shù)列健蕊，一次比較兩個(gè)元素菱阵，如果他們的順序錯(cuò)誤就把他們交換過來缩功。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成嫡锌。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端虑稼。
冒泡排序?qū)個(gè)項(xiàng)目需要O(n^{2})的比較次數(shù)势木，且可以原地排序。盡管這個(gè)算法是最簡單了解和實(shí)作的排序算法之一跟压，但它對(duì)于少數(shù)元素之外的數(shù)列排序是很沒有效率的胰蝠。
冒泡排序是與插入排序擁有相等的執(zhí)行時(shí)間震蒋，但是兩種法在需要的交換次數(shù)卻很大地不同。在最壞的情況查剖，冒泡排序需要O(n^{{2})次交換钾虐，而插入排序只要最多O(n)交換笋庄。冒泡排序的實(shí)現(xiàn)（類似下面）通常會(huì)對(duì)已經(jīng)排序好的數(shù)列拙劣地執(zhí)行（O(n}{2})），而插入排序在這個(gè)例子只需要O(n)個(gè)運(yùn)算直砂。因此很多現(xiàn)代的算法教科書避免使用冒泡排序菌仁，而用插入排序取代之静暂。冒泡排序如果能在內(nèi)部循環(huán)第一次執(zhí)行時(shí)，使用一個(gè)旗標(biāo)來表示有無需要交換的可能洽蛀，也有可能把最好的復(fù)雜度降低到O(n)摹迷。在這個(gè)情況郊供，在已經(jīng)排序好的數(shù)列就無交換的需要峡碉。若在每次走訪數(shù)列時(shí)，把走訪順序和比較大小反過來驮审，也可以稍微地改進(jìn)效率吉执。有時(shí)候稱為往返排序，因?yàn)樗惴〞?huì)從數(shù)列的一端到另一端之間穿梭往返塔拳。
2.算法實(shí)現(xiàn)
1.比較相鄰的元素。如果第一個(gè)比第二個(gè)大靠抑，就交換他們兩個(gè)。
2.對(duì)每一對(duì)相鄰元素作同樣的工作颂碧，從開始第一對(duì)到結(jié)尾的最后一對(duì)荠列。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)载城。
3.針對(duì)所有的元素重復(fù)以上的步驟肌似，除了最后一個(gè)。
4.持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟诉瓦，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

C#實(shí)現(xiàn)

/// <summary>
/// 冒泡排序
/// </summary>
public void BubbleSort(int[] R)
{
int i, j, temp; //交換標(biāo)志
bool exchange;
for (i = 0; i < R.Length; i++) //最多做R.Length-1趟排序
{
exchange = false; //本趟排序開始前睬澡，交換標(biāo)志應(yīng)為假
for (j = R.Length - 2; j >= i; j--)
{
if (R[j + 1] < R[j]) //交換條件
{
temp = R[j + 1];
R[j + 1] = R[j];
R[j] = temp;
exchange = true; //發(fā)生了交換，故將交換標(biāo)志置為真
}
}
if (!exchange) //本趟排序未發(fā)生交換煞聪，提前終止算法
{
break;
}
}
}

五 歸并 排序

/// <summary>
/// 歸并排序之歸：歸并排序入口
/// </summary>
/// <param name="data">無序的數(shù)組</param>
/// <returns>有序數(shù)組</returns>
/// <author>Lihua(www.zivsoft.com)</author>
int[] MergeSort(int[] data)
{
//取數(shù)組中間下標(biāo)
int middle = data.Length / 2;
//初始化臨時(shí)數(shù)組let,right斗躏，并定義result作為最終有序數(shù)組
int[] left = new int[middle], right = new int[middle], result = new int[data.Length];
if (data.Length % 2 != 0)//若數(shù)組元素奇數(shù)個(gè)昔脯，重新初始化右臨時(shí)數(shù)組
{
right = new int[middle + 1];
}
if (data.Length <= 1)//只剩下1 or 0個(gè)元數(shù)，返回云稚，不排序
{
return data;
}
int i = 0, j = 0;
foreach (int x in data)//開始排序
{
if (i < middle)//填充左數(shù)組
{
left[i] = x;
i++;
}
else//填充右數(shù)組
{
right[j] = x;
j++;
}
}
left = MergeSort(left);//遞歸左數(shù)組
right = MergeSort(right);//遞歸右數(shù)組
result = Merge(left, right);//開始排序
return result;
}
/// <summary>
/// 歸并排序之并:排序在這一步
/// </summary>
/// <param name="a">左數(shù)組</param>
/// <param name="b">右數(shù)組</param>
/// <returns>合并左右數(shù)組排序后返回</returns>
int[] Merge(int[] a, int[] b)
{
//定義結(jié)果數(shù)組隧饼，用來存儲(chǔ)最終結(jié)果
int[] result = new int[a.Length + b.Length];
int i = 0, j = 0, k = 0;
while (i < a.Length && j < b.Length)
{
if (a[i] < b[j])//左數(shù)組中元素小于右數(shù)組中元素
{
result[k++] = a[i++];//將小的那個(gè)放到結(jié)果數(shù)組
}
else//左數(shù)組中元素大于右數(shù)組中元素
{
result[k++] = b[j++];//將小的那個(gè)放到結(jié)果數(shù)組
}
}
while (i < a.Length)//這里其實(shí)是還有左元素静陈，但沒有右元素
{
result[k++] = a[i++];
}
while (j < b.Length)//右右元素，無左元素
{
result[k++] = b[j++];
}
return result;//返回結(jié)果數(shù)組
}

六 基數(shù)排序

//基數(shù)排序
public int[] RadixSort(int[] ArrayToSort, int digit)
{
//low to high digit
for (int k = 1; k <= digit; k++)
{
//temp array to store the sort result inside digit
int[] tmpArray = new int[ArrayToSort.Length];
//temp array for countingsort
int[] tmpCountingSortArray = new int[10] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
//CountingSort
for (int i = 0; i < ArrayToSort.Length; i++)
{
//split the specified digit from the element
int tmpSplitDigit = ArrayToSort[i] / (int) Math.Pow(10, k - 1) - (ArrayToSort[i] / (int) Math.Pow(10, k)) * 10;
tmpCountingSortArray[tmpSplitDigit] += 1;
}
for (int m = 1; m < 10; m++)
{
tmpCountingSortArray[m] += tmpCountingSortArray[m - 1];
}
//output the value to result
for (int n = ArrayToSort.Length - 1; n >= 0; n--)
{
int tmpSplitDigit = ArrayToSort[n] / (int) Math.Pow(10, k - 1) - (ArrayToSort[n] / (int) Math.Pow(10, k)) * 10;
tmpArray[tmpCountingSortArray[tmpSplitDigit] - 1] = ArrayToSort[n];
tmpCountingSortArray[tmpSplitDigit] -= 1;
}
//copy the digit-inside sort result to source array
for (int p = 0; p < ArrayToSort.Length; p++)
{
ArrayToSort[p] = tmpArray[p];
}
}
return ArrayToSort;
}

七 計(jì)數(shù)排序

//計(jì)數(shù)排序
/// <summary>
/// counting sort
/// </summary>
/// <param name="arrayA">input array</param>
/// <param name="arrange">the value arrange in input array</param>
/// <returns></returns>
public int[] CountingSort(int[] arrayA, int arrange)
{
//array to store the sorted result,
//size is the same with input array.
int[] arrayResult = new int[arrayA.Length];
//array to store the direct value in sorting process
//include index 0;
//size is arrange+1;
int[] arrayTemp = new int[arrange + 1];
//clear up the temp array
for (int i = 0; i <= arrange; i++)
{
arrayTemp[i] = 0;
}
//now temp array stores the count of value equal
for (int j = 0; j < arrayA.Length; j++)
{
arrayTemp[arrayA[j]] += 1;
}
//now temp array stores the count of value lower and equal
for (int k = 1; k <= arrange; k++)
{
arrayTemp[k] += arrayTemp[k - 1];
}
//output the value to result
for (int m = arrayA.Length - 1; m >= 0; m--)
{
arrayResult[arrayTemp[arrayA[m]] - 1] = arrayA[m];
arrayTemp[arrayA[m]] -= 1;
}
return arrayResult;
}

九 堆排序

一種是數(shù)據(jù)結(jié)構(gòu)窿给，邏輯上是一顆完全二叉樹贵白，存儲(chǔ)上是一個(gè)數(shù)組對(duì)象（二叉堆）率拒。
另一種是垃圾收集存儲(chǔ)區(qū)，是軟件系統(tǒng)可以編程的內(nèi)存區(qū)域猬膨。
本文所說的堆指的是前者角撞，另外，這篇文章中堆中元素的值均以整形為例
堆排序的時(shí)間復(fù)雜度是O(nlog2n),與快速排序達(dá)到相同的時(shí)間復(fù)雜度. 但是在實(shí)際應(yīng)用中,我們往往采用快速排序而不是堆排序. 這是因?yàn)榭焖倥判虻囊粋€(gè)好的實(shí)現(xiàn),往往比堆排序具有更好的表現(xiàn). 堆排序的主要用途,是在形成和處理優(yōu)先級(jí)隊(duì)列方面. 另外, 如果計(jì)算要求是類優(yōu)先級(jí)隊(duì)列(比如, 只要返回最大或者最小元素, 只有有限的插入要求等), 堆同樣是很適合的數(shù)據(jù)結(jié)構(gòu).

堆排序
堆排序是一種選擇排序谒所。是不穩(wěn)定的排序方法热康。時(shí)間復(fù)雜度為O(nlog2n)劣领。
堆排序的特點(diǎn)是：在排序過程中，將排序數(shù)組看成是一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)尖淘，利用完全二叉樹中雙親節(jié)點(diǎn)和孩子節(jié)點(diǎn)之間的內(nèi)在關(guān)系奕锌，在當(dāng)前無序區(qū)中選擇關(guān)鍵字最大(或最小)的記錄村生。

基本思想
1.將要排序的數(shù)組創(chuàng)建為一個(gè)大根堆。大根堆的堆頂元素就是這個(gè)堆中最大的元素趁桃。
2.將大根堆的堆頂元素和無序區(qū)最后一個(gè)元素交換辽话，并將無序區(qū)最后一個(gè)位置例入有序區(qū)卫病，然后將新的無序區(qū)調(diào)整為大根堆。
重復(fù)操作忽肛，無序區(qū)在遞減村砂，有序區(qū)在遞增。
初始時(shí)础废，整個(gè)數(shù)組為無序區(qū)，第一次交換后無序區(qū)減一罕模，有序區(qū)增一。
每一次交換淑掌，都是大根堆的堆頂元素插入有序區(qū)蒿讥，所以有序區(qū)保持是有序的抛腕。

C#實(shí)現(xiàn)

//堆排序算法（傳遞待排數(shù)組名，即：數(shù)組的地址担敌。故形參數(shù)組的各種操作反應(yīng)到實(shí)參數(shù)組上）
private void HeapSortFunction(int[] array)
{
try
{
BuildMaxHeap(array); //創(chuàng)建大頂推（初始狀態(tài)看做：整體無序）
for (int i = array.Length -1; i >0; i--)
{
Swap(ref array[0], ref array[i]); //將堆頂元素依次與無序區(qū)的最后一位交換（使堆頂元素進(jìn)入有序區(qū)）
MaxHeapify(array, 0, i); //重新將無序區(qū)調(diào)整為大頂堆
}
}
catch (Exception ex)
{ }
}

    ///<summary>
    /// 創(chuàng)建大頂推（根節(jié)點(diǎn)大于左右子節(jié)點(diǎn)）
    ///</summary>
    ///<param name="array">待排數(shù)組</param>
 private void BuildMaxHeap(int[] array)
    {
        try
        {
            //根據(jù)大頂堆的性質(zhì)可知：數(shù)組的前半段的元素為根節(jié)點(diǎn)摔敛，其余元素都為葉節(jié)點(diǎn)
            for (int i = array.Length /2-1; i >=0; i--) //從最底層的最后一個(gè)根節(jié)點(diǎn)開始進(jìn)行大頂推的調(diào)整
            {
                MaxHeapify(array, i, array.Length); //調(diào)整大頂堆
            }
        }
        catch (Exception ex)
        { }
    }

    ///<summary>
    /// 大頂推的調(diào)整過程
    ///</summary>
    ///<param name="array">待調(diào)整的數(shù)組</param>
    ///<param name="currentIndex">待調(diào)整元素在數(shù)組中的位置（即：根節(jié)點(diǎn)）</param>
    ///<param name="heapSize">堆中所有元素的個(gè)數(shù)</param>
 private void MaxHeapify(int[] array, int currentIndex, int heapSize)
    {
        try
        {
           int left =2* currentIndex +1;    //左子節(jié)點(diǎn)在數(shù)組中的位置
     int right =2* currentIndex +2;   //右子節(jié)點(diǎn)在數(shù)組中的位置
     int large = currentIndex;   //記錄此根節(jié)點(diǎn)全封、左子節(jié)點(diǎn)桃犬、右子節(jié)點(diǎn) 三者中最大值的位置
            if (left < heapSize && array[left] > array[large])  //與左子節(jié)點(diǎn)進(jìn)行比較
            {
                large = left;
            }
            if (right < heapSize && array[right] > array[large])    //與右子節(jié)點(diǎn)進(jìn)行比較
            {
                large = right;
            }
            if (currentIndex != large)  //如果 currentIndex != large 則表明 large 發(fā)生變化（即：左右子節(jié)點(diǎn)中有大于根節(jié)點(diǎn)的情況）
            {
                Swap(ref array[currentIndex], ref array[large]);    //將左右節(jié)點(diǎn)中的大者與根節(jié)點(diǎn)進(jìn)行交換（即：實(shí)現(xiàn)局部大頂堆）
                MaxHeapify(array, large, heapSize); //以上次調(diào)整動(dòng)作的large位置（為此次調(diào)整的根節(jié)點(diǎn)位置），進(jìn)行遞歸調(diào)整
            }
        }
        catch (Exception ex)
        { }
    }

    ///<summary>
    /// 交換函數(shù)
    ///</summary>
    ///<param name="a">元素a</param>
    ///<param name="b">元素b</param>
 private void Swap(refint a, refint b)
    {
        int temp =0;
        temp = a;
        a = b;
        b = temp;
    }