本章的所有代碼可以訪問(wèn)這里

---

一、排序的概念及其運(yùn)用

1.1排序的概念

排序：所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來(lái)的操作。
穩(wěn)定性：假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過(guò)排序，這些記錄的相對(duì)次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱(chēng)這種排序算法是穩(wěn)定的；否則稱(chēng)為不穩(wěn)定的。
內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。
外部排序：數(shù)據(jù)元素太多不能同時(shí)放在內(nèi)存中，根據(jù)排序過(guò)程的要求不能在內(nèi)外存之間移動(dòng)數(shù)據(jù)的排序。

1.2 常見(jiàn)的排序算法

二、常見(jiàn)排序算法的實(shí)現(xiàn)

1、直接插入排序

• 基本思想
  直接插入排序是一種簡(jiǎn)單的插入排序法，其基本思想是：把待排序的記錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個(gè)新的有序序列 。

<實(shí)際中我們玩撲克牌時(shí)，就用了插入排序的思想>

• 步驟
  假設(shè)我們進(jìn)行升序排序
  

1. 我們首先認(rèn)為我們第一個(gè)數(shù)據(jù)是有序的。

2. 取一個(gè)數(shù)據(jù)data，將已排序的元素序列從后往前遍歷

3. 如果遍歷過(guò)程中發(fā)現(xiàn)已排序的元素序列中的某個(gè)數(shù)據(jù)largeData大于data那我們就將數(shù)據(jù)largeData向后移動(dòng)一個(gè)單位，然后繼續(xù)向前遍歷。如果已排序的元素序列中的某個(gè)數(shù)據(jù)smallerData小于data,那我們就將數(shù)據(jù)data放到smallerData的后面，然后就不需要向前遍歷了,因?yàn)?strong>已排序的元素序列經(jīng)過(guò)上面的2-3步驟后新來(lái)的數(shù)據(jù)data也被放到了正確的位置。
   
   

4. 所以我們對(duì)許多數(shù)據(jù)進(jìn)行排序就被轉(zhuǎn)化為上面2-3步驟的循環(huán)了。

動(dòng)圖演示

• 代碼實(shí)現(xiàn)

//直接插入排序
void InsertSort(int* a,int n)
{//排序 for (int i = 0; i + 1 < n; i++){//end是有序數(shù)列的最后一個(gè)位置的下標(biāo)int end = i;int tmp = a[end + 1];//end >= 0 防止在--end時(shí)數(shù)組越界while (end >= 0 && tmp < a[end]){a[end +1] = a[end];--end;}a[end+1] = tmp;}
}

• 直接插入排序的特性總結(jié)：

1. 元素集合越接近有序，直接插入排序算法的時(shí)間效率越高（因?yàn)閿?shù)據(jù)越接近于有序，向后挪動(dòng)的次數(shù)就越小）
2. 最壞情況下為$O(n^2)$，此時(shí)待排序列為逆序，或者說(shuō)接近逆序
   最好情況下為$O(n)$，此時(shí)待排序列為升序，或者說(shuō)接近升序
3. 空間復(fù)雜度：$O(1)$，它是一種穩(wěn)定的排序算法
4. 穩(wěn)定性：穩(wěn)定

2、希爾排序

希爾排序法的步驟是：
先選定一個(gè)小于N(N為數(shù)組的個(gè)數(shù))的整數(shù)gap，把所有數(shù)據(jù)分成gap個(gè)組，所有距離為gap的數(shù)據(jù)分在同一組內(nèi)，并對(duì)每一組的元素進(jìn)行直接插入排序。然后取新的gap（新的gap要小于上一個(gè)gap），重復(fù)上述分組和排序的工作。當(dāng)?shù)竭_(dá)gap=1時(shí)，所有數(shù)據(jù)在同一組內(nèi)排好順序。

希爾排序法的思想是：
希爾排序先將待排序列通過(guò)gap分組進(jìn)行預(yù)排序（gap>1時(shí)都是預(yù)排序），使待排序列接近有序，然后再對(duì)該序列進(jìn)行一次插入排序（gap=1時(shí)其實(shí)就是插入排序），此時(shí)插入排序的時(shí)間復(fù)雜度接近于O(N)

代碼實(shí)現(xiàn)

//希爾排序   正常一組一組排序
void ShellSort(int* a,int n)
{//定義第一次gap的值  int gap = n;//多次預(yù)排序，gap=1時(shí)是直接排序while (gap > 1){//減小gap的值直到1gap = gap / 3 + 1;//多趟排序for (int j = 0; j < gap; j++){//單趟排序  i是當(dāng)前有序序列最后一個(gè)位置的下標(biāo)for (int i = j; i + gap < n; i += gap){int end = i;//記錄一下待插入的數(shù)據(jù)int tmp = a[end + gap];//end >= 0 防止在end -=gap 時(shí)數(shù)組越界while (end >= 0 && tmp < a[end]){a[end + gap] = a[end];end -= gap;}a[end + gap] = tmp;}}}
}

• 希爾排序的特性總結(jié)：

1. 希爾排序是對(duì)直接插入排序的優(yōu)化。
2. 當(dāng)gap > 1時(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時(shí)，數(shù)組已經(jīng)接近有序的了，這樣就會(huì)很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。我們實(shí)現(xiàn)后可以進(jìn)行性能測(cè)試的對(duì)比。
3. 希爾排序的時(shí)間復(fù)雜度不好計(jì)算，因?yàn)間ap的取值方法很多，導(dǎo)致很難去計(jì)算，因此在好些書(shū)中給出的希爾排序的時(shí)間都不固定。
4. 時(shí)間復(fù)雜度平均：$O(N^{1.3})$
5. 空間復(fù)雜度：$O(1)$
6. 穩(wěn)定性：不穩(wěn)定

3、選擇排序

基本思想：
每一次從待排序的數(shù)據(jù)元素中選出最小和最大的一個(gè)元素，存放在序列的起始位置和末尾位置，然后起始位置向后移動(dòng)一個(gè)單位，末尾位置向前移動(dòng)一個(gè)單位，直到全部待排序的數(shù)據(jù)元素排完 。

步驟：
遍歷一遍整個(gè)數(shù)組，選出最大值和最小值，第一次將最小值放到a[0]最大值a[n-1],第二次將最小值放到a[1]最大值a[n-2]，直到下標(biāo)$m>=n?m?1$結(jié)束程序。

動(dòng)態(tài)演示
（下圖演示的是一次只選一個(gè)最小值的算法，我們一次選出最大和最小，比圖中的更高效一些）

代碼實(shí)現(xiàn)

//選擇排序
void SelectSort(int* a, int n)
{//多趟排序int begin = 0;int end = n - 1;while (begin < end){//先假設(shè) a[0] 位置既是最小值又是最大值//mini是最小值的下標(biāo)，maxi是最大位置的下標(biāo)int mini = begin, maxi = begin;//單趟遍歷，選出最大值于最小值for (int i = begin; i <=end; ++i){if (a[i] > a[maxi]){maxi = i;}else if (a[i] < a[mini]){mini = i;}}Swap(&a[begin], &a[mini]);if (begin == maxi){maxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}

直接選擇排序的特性總結(jié)：

1. 直接選擇排序思考非常好理解，但是效率不是很好。實(shí)際中很少使用
2. 時(shí)間復(fù)雜度：O(N^2)
3. 空間復(fù)雜度：O(1)
4. 穩(wěn)定性：不穩(wěn)定

4、堆排序

堆排序(Heapsort)是指利用堆積樹(shù)（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種。它是通過(guò)堆來(lái)進(jìn)行選擇數(shù)據(jù)。需要注意的是排升序要建大堆，排降序建小堆。

堆排序詳情請(qǐng)看這里

堆排序的特性總結(jié)：

1. 堆排序使用堆來(lái)選數(shù)，效率就高了很多。
2. 時(shí)間復(fù)雜度：O(N*logN)
3. 空間復(fù)雜度：O(1)
4. 穩(wěn)定性：不穩(wěn)定

5、冒泡排序

基本思想：
兩兩進(jìn)行比較，左邊大于右邊就進(jìn)行交換，走完一趟就排序好一個(gè)數(shù)。

代碼實(shí)現(xiàn)

//冒泡排序
int BubbleSort(int*a,int n)
{for (int j = 0; j < n; j++){//end是排序數(shù)組的最后一個(gè)需要排序元素的下標(biāo)int end = n - 1 - j;//定義一個(gè)交換標(biāo)志int exchange = 0;for (int i = 0; i < end; i++){if (a[i] > a[i + 1]){Swap(&a[i], &a[i + 1]);exchange = 1;}}// 一趟冒泡過(guò)程中，沒(méi)有發(fā)生交換，說(shuō)明已經(jīng)有序了，不需要再處理if (exchange == 0){break;}}
}

冒泡排序的特性總結(jié)：

1. 冒泡排序是一種非常容易理解的排序
2. 時(shí)間復(fù)雜度：O(N^2)
3. 空間復(fù)雜度：O(1)
4. 穩(wěn)定性：穩(wěn)定

6、快速排序

基本思路：
任取待排序元素序列中的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過(guò)程，直到所有元素都排列在相應(yīng)位置上為止。

6.1霍爾法

步驟：

1. 首先選出一個(gè)key值作為基準(zhǔn)值，通常選擇待排序列的最左邊的值作為key值。
2. 定義兩個(gè)下標(biāo)，left與right,其中l(wèi)eft指向待排序列的最左邊值的下標(biāo)，right指向待排序列最右邊的下標(biāo)。
3. 如果我們選擇了最左邊作為key值，我們就要讓right位置判斷a[right] < key如果成立，那就讓right暫時(shí)停下來(lái)；如果不成立，就讓right- -,直到找到一個(gè)位置a[right] < key ,找到后，right就暫時(shí)停下來(lái)。（需要注意的是：若選擇最左邊的數(shù)據(jù)作為key，則需要right先走；若選擇最右邊的數(shù)據(jù)作為key，則需要begin先走）。
4. right停下來(lái)之后，我們就要讓左邊的left的位置判斷 a[left] > key 如果成立，就將a[left]與a[right]進(jìn)行交換 ，如果不成立我們就將left++,直到找到一個(gè)位置a[left] > key ,找到后就與a[right]進(jìn)行交換。
5. 然后重復(fù)3-4,直到 left=right 時(shí)，我們將key與a[ left ] ( 此時(shí)a[left]=a[right] )進(jìn)行交換，此時(shí)key就到了正確的位置，key將數(shù)組分成了兩部分，此時(shí)key的左邊都比key小，key的右邊都比key大，一次單趟排序完成，一次單趟排序搞定了一個(gè)數(shù)據(jù)。
6. 我們?cè)賹?duì)上一次的key的左右邊的數(shù)組再進(jìn)行上面的步驟，直到每個(gè)被分割的小區(qū)間都有序了，整個(gè)數(shù)組的排序就完成了。（最后當(dāng)左右序列只有一個(gè)數(shù)據(jù)，或是左右序列不存在時(shí)，其實(shí)小區(qū)間就已經(jīng)有序了）

動(dòng)態(tài)演示

代碼實(shí)現(xiàn)

//快速排序   hoare法   void QuickSort(int* a, int begin, int end)
{//當(dāng)區(qū)間只有一個(gè)值時(shí)，或區(qū)間不存在時(shí)退出遞歸if (begin >= end){return;}//left是閉區(qū)間最最左邊的下標(biāo)，right是最右邊位置的下標(biāo)int left = begin, right = end;//選擇最左邊作為key值int keyi = left;//一趟排序while (left < right){//右邊先走，找到a[right]<key的位置while (left < right && a[right] >= a[keyi]){--right;}//左邊后走，找到a[left]>key的位置while (left < right && a[left] <= a[keyi]){++left;}//交換左右兩邊的值,如果left == right了，也沒(méi)有必要交換了。if (left != right){Swap(&a[left], &a[right]);}}//交換左右兩邊的值,如果keyi == left了，也沒(méi)有必要交換了。if (keyi != left){Swap(&a[keyi], &a[left]);}keyi = left;//此時(shí)區(qū)間被分割為[begin,keyi-1] keyi [keyi+1,end]//注意傳遞的是begin,不是0,中間遞歸時(shí)不一定是從0開(kāi)始的區(qū)間，0是一個(gè)常量，begin是一個(gè)變量。QuickSort(a, begin, keyi-1);QuickSort(a, keyi+1, end);
}

6.2挖坑法

步驟：

1. 先將待排序列的最左邊的值定為key,用一個(gè)臨時(shí)變量保存key的值同時(shí)該位置的下標(biāo)定為第一個(gè)坑位hole。
2. 右邊right尋找比key小的值，找到后放進(jìn)坑位中，同時(shí)將坑位的位置更新為right。
3. 左邊left尋找比key大的值，找到后放進(jìn)坑位中，同時(shí)將坑位的位置更新為left。
4. 重復(fù)2-3步驟直到left==right，然后將key放到相遇位置，a[left]=key(或a[right]=key)
5. 此時(shí)單趟排序就排序好了，key的左邊的值比key小，key右邊的值比key大，key到了正確的位置，區(qū)間被分為兩份，一次單趟排序好一個(gè)數(shù)。
6. 再對(duì)分割后的區(qū)間，進(jìn)行多次上述的單趟排序，整個(gè)數(shù)組就有序了！
   

//快速排序  挖坑法
void QuickSort(int* a, int begin, int end)
{//當(dāng)區(qū)間只有一個(gè)值時(shí)，或區(qū)間不存在時(shí)退出遞歸if (begin >= end){return;}int left = begin, right = end;int keyi = left;//剛開(kāi)始時(shí)keyi的位置作為坑位int hole = keyi;int key = a[keyi];while (left < right){while (left < right && a[right] >= key){--right;}a[hole] = a[right];hole = right;while (left < right && a[left] <= key){++left;}a[hole] = a[left];hole = left;}a[hole] = key;keyi = hole;//此時(shí)區(qū)間被分割為[begin,keyi-1] keyi [keyi+1,end]//注意傳遞的是begin,不是0,中間遞歸時(shí)不一定是從0開(kāi)始的區(qū)間，0是一個(gè)常量，begin是一個(gè)變量。QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

6.3前后指針?lè)?/h3>

步驟：

1. 初始時(shí)，我們選定待排序的數(shù)據(jù)最左邊作為key，定義prev也在待排序的數(shù)據(jù)最左邊，定義cur在待排序的數(shù)據(jù)最左邊+1。
2. cur向前找比key小的值，找到后停下來(lái)，然后++prev，交換prev位置和cur位置的值，當(dāng)prev與cur拉開(kāi)差距時(shí)，prev與cur之間夾的值都是大于等于key的值。
3. 最后cur剛好越界時(shí)，數(shù)組遍歷完畢，交換a[prev]與key,此時(shí)key到了正確的位置，區(qū)間被分為兩份，一次單趟排序好一個(gè)數(shù)。
4. 再對(duì)分割后的區(qū)間，進(jìn)行多次上述的單趟排序，整個(gè)數(shù)組就有序了！

//快速排序  前后指針?lè)?/span>
void QuickSort(int* a, int begin, int end)
{//當(dāng)區(qū)間只有一個(gè)值時(shí)，或區(qū)間不存在時(shí)退出遞歸if (begin >= end){return;}int prev = begin , cur = begin + 1;int keyi = begin;while (prev <= cur && cur <= end){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}++cur;}Swap(&a[keyi], &a[prev]);keyi = prev;//此時(shí)區(qū)間被分割為[begin,keyi-1] keyi [keyi+1,end]//注意傳遞的是begin,不是0,中間遞歸時(shí)不一定是從0開(kāi)始的區(qū)間，0是一個(gè)常量，begin是一個(gè)變量。QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

快速排序的特性總結(jié)：

1. 快速排序整體的綜合性能和使用場(chǎng)景都是比較好的，所以才敢叫快速排序
2. 時(shí)間復(fù)雜度：O(N*logN)
   
3. 空間復(fù)雜度：O(logN)
4. 穩(wěn)定性：不穩(wěn)定

7、快速排序非遞歸

快速排序的非遞歸實(shí)現(xiàn)要依賴(lài)棧，我們對(duì)快速排序進(jìn)行遞歸時(shí)傳遞的關(guān)鍵數(shù)據(jù)是區(qū)間的下標(biāo)，只有拿到了區(qū)間的下標(biāo)我們才能進(jìn)行正確的排序。
因此我們應(yīng)該用利用棧的特性將區(qū)間的下標(biāo)存放起來(lái)。

代碼實(shí)現(xiàn)：

//單趟排序
int Partion3(int* a ,int begin ,int end)
{int prev = begin , cur = begin + 1;int keyi = begin;while (prev <= cur && cur <= end){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}++cur;}Swap(&a[keyi], &a[prev]);keyi = prev;return keyi;
}
//快速排序的非遞歸實(shí)現(xiàn)
void QuickSortNonR(int* a ,int begin ,int end)
{Stack st;StackInit(&st);StackPush(&st, begin);StackPush(&st, end);while (!StackEmpty(&st)){int right = StackTop(&st);StackPop(&st);int left = StackTop(&st);StackPop(&st);//一趟排序int keyi = Partion3(a, left, right);//此時(shí)區(qū)間被劃分為[left,keyi-1]keyi[keyi+1,right]if (keyi + 1 < right){StackPush(&st, keyi + 1);StackPush(&st, right);}if (left < keyi - 1){StackPush(&st, left);StackPush(&st, keyi - 1);}}StackDestroy(&st);
}