本章的所有代碼可以訪問這里

---

一、排序的概念及其運用

1.1排序的概念

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

1.2 常見的排序算法

二、常見排序算法的實現

1、直接插入排序

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

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

• 步驟
  假設我們進行升序排序
  

1. 我們首先認為我們第一個數據是有序的。

2. 取一個數據data，將已排序的元素序列從后往前遍歷

3. 如果遍歷過程中發(fā)現已排序的元素序列中的某個數據largeData大于data那我們就將數據largeData向后移動一個單位，然后繼續(xù)向前遍歷。如果已排序的元素序列中的某個數據smallerData小于data,那我們就將數據data放到smallerData的后面，然后就不需要向前遍歷了,因為已排序的元素序列經過上面的2-3步驟后新來的數據data也被放到了正確的位置。
   
   

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

動圖演示

• 代碼實現

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

• 直接插入排序的特性總結：

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

2、希爾排序

希爾排序法的步驟是：
先選定一個小于N(N為數組的個數)的整數gap，把所有數據分成gap個組，所有距離為gap的數據分在同一組內，并對每一組的元素進行直接插入排序。然后取新的gap（新的gap要小于上一個gap），重復上述分組和排序的工作。當到達gap=1時，所有數據在同一組內排好順序。

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

代碼實現

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

• 希爾排序的特性總結：

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

3、選擇排序

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

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

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

代碼實現

//選擇排序
void SelectSort(int* a, int n)
{//多趟排序int begin = 0;int end = n - 1;while (begin < end){//先假設 a[0] 位置既是最小值又是最大值//mini是最小值的下標，maxi是最大位置的下標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;}
}

直接選擇排序的特性總結：

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

4、堆排序

堆排序(Heapsort)是指利用堆積樹（堆）這種數據結構所設計的一種排序算法，它是選擇排序的一種。它是通過堆來進行選擇數據。需要注意的是排升序要建大堆，排降序建小堆。

堆排序詳情請看這里

堆排序的特性總結：

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

5、冒泡排序

基本思想：
兩兩進行比較，左邊大于右邊就進行交換，走完一趟就排序好一個數。

代碼實現

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

冒泡排序的特性總結：

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

6、快速排序

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

6.1霍爾法

步驟：

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

動態(tài)演示

代碼實現

//快速排序   hoare法   void QuickSort(int* a, int begin, int end)
{//當區(qū)間只有一個值時，或區(qū)間不存在時退出遞歸if (begin >= end){return;}//left是閉區(qū)間最最左邊的下標，right是最右邊位置的下標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了，也沒有必要交換了。if (left != right){Swap(&a[left], &a[right]);}}//交換左右兩邊的值,如果keyi == left了，也沒有必要交換了。if (keyi != left){Swap(&a[keyi], &a[left]);}keyi = left;//此時區(qū)間被分割為[begin,keyi-1] keyi [keyi+1,end]//注意傳遞的是begin,不是0,中間遞歸時不一定是從0開始的區(qū)間，0是一個常量，begin是一個變量。QuickSort(a, begin, keyi-1);QuickSort(a, keyi+1, end);
}

6.2挖坑法

步驟：

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

//快速排序  挖坑法
void QuickSort(int* a, int begin, int end)
{//當區(qū)間只有一個值時，或區(qū)間不存在時退出遞歸if (begin >= end){return;}int left = begin, right = end;int keyi = left;//剛開始時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;//此時區(qū)間被分割為[begin,keyi-1] keyi [keyi+1,end]//注意傳遞的是begin,不是0,中間遞歸時不一定是從0開始的區(qū)間，0是一個常量，begin是一個變量。QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

6.3前后指針法

步驟：

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

//快速排序  前后指針法
void QuickSort(int* a, int begin, int end)
{//當區(qū)間只有一個值時，或區(qū)間不存在時退出遞歸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;//此時區(qū)間被分割為[begin,keyi-1] keyi [keyi+1,end]//注意傳遞的是begin,不是0,中間遞歸時不一定是從0開始的區(qū)間，0是一個常量，begin是一個變量。QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

快速排序的特性總結：

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

7、快速排序非遞歸

快速排序的非遞歸實現要依賴棧，我們對快速排序進行遞歸時傳遞的關鍵數據是區(qū)間的下標，只有拿到了區(qū)間的下標我們才能進行正確的排序。
因此我們應該用利用棧的特性將區(qū)間的下標存放起來。

代碼實現：

//單趟排序
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;
}
//快速排序的非遞歸實現
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);//此時區(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);
}