目錄

文章目錄

前言

一.排序的基本概念

1.什么是就地排序

2.什么是內部排序和外部排序

3.什么是穩定排序

4.判定一個排序算法的是穩定的

二.插入排序算法

1.直接插入排序

1.1基本思想

1.2復雜度

1.3穩定性

1.4代碼演示

2.折半插入排序

2.1基本思想

2.2性能

3.2-路插入排序算法

4.希爾排序

4.1基本思想

4.2?性能

4.3Hibbard增量序列

4.4更多的增量序列

4.5代碼演示

三.交換排序

1.冒泡排序

1.1算法思想

1.2關于冒泡的優化

1.3復雜度分析

1.4如何用兩個棧實現冒泡

1.5詳細解析

1.6代碼演示

2.快速排序

2.1算法思想

2.2復雜度分析

2.3快速排序的穩定性從哪里來

2.4代碼演示

四.歸并和計數排序

1.歸并排序

1.1算法思想

1.2復雜度分析

1.3代碼演示

2.計數排序

2.1算法思想

2.2穩定性

2.3復雜度分析

3.桶排序

3.1桶排序的思想

3.2關于桶排序的算法分析

3.3桶排序適用情況

4.基數排序

4.1算法思想

4.2復雜度分析

五.選擇排序（二叉堆）

1.堆

2.二叉堆

3. 二叉堆的存儲結構

4. 小頂二叉堆常見的操作

5.簡單的選擇排序與堆排序代碼演示

---

---

前言

排序算法的重要性不言而喻在算法競賽中經常考到因此我們要好好學習！

---

一.排序的基本概念

1.什么是就地排序

使用恒定的額外空間，只需要使用他給你的數據
一個就地排序算法使用恒定的的額外空間來產生輸出（僅修改給定的數組）。它僅通過修改線性表中元素的順序來對線性表進行排序。
例如，插入排序和選擇排序是就地排序算法，因為它們不使用任何額外的空間來對線性表進行排序。而歸并排序和計數排序的經典實現就不是就地排序算法

2.什么是內部排序和外部排序

待排序數據，是否可以一次性的載入到內存中
當所有待排序記錄不能被一次載入內存進行處理時，這樣的排序就被稱為外部排序。
外部排序通常應用在待排序記錄的數量非常大的時候。歸并排序以及它的變體都是典型的外部排序算法。外部排序通常與硬盤、CD等外部存儲器（輔存）關聯在一起。當所有待排序記錄可以一次載入內存時，則稱為內部排序。

3.什么是穩定排序

判斷相同的關鍵字，排序以后，相對位置的變化，處理鍵值對的時候
當我們對可能存在重復鍵的鍵值對（例如，人名作為鍵，其詳細信息作為值）按照鍵對這些對象 進行排序時，穩定性就顯得至關重要

4.判定一個排序算法的是穩定的

如果兩個具有相等關鍵字的對象在排序前后的相對位置沒有發生變化，則認為排序算法是穩定的。可以形式化地描述為：
設A表示一個待排序的數組， <表示數組A的一個嚴格的弱排序（即有重復元素）。一個排序算法穩定，當且僅當i < j^A[i]≡A[j] ，且隱含π(i) < π(j)，其中π表示排序后的序列（排序算法將A[i]移動到了π(i)的位置，將A[j]移動到了π[j]的位置，但是i和j的相對位置保持不變)。

圖中展示的就是穩定排序的例子，簡單來講，排序前，青色球 10 在藍色球 10 的前面，那么排序后兩者的相對位置并沒有改變，青色球 10 還是在紅色球的前面；排序前藍色球 20 在青色球 20 的前面，則排序后兩者的兩者的位置沒有發生變化，依舊是藍色在青色的前面

簡而言之，排序前后序列中鍵值相等的元素的相對位置沒有發生變化的就是穩定排序

二.插入排序算法

1.直接插入排序

在玩撲克牌的時候，我們抽到一張牌的時候，都是將它插入到當前手中牌的合適位置的。直接插入排序也是這樣的思想

1.1基本思想

插入排序的思想是：
將待排序序列分成兩個序列，前面的序列保持有序，依次選取后面的序列的元素，在前面的序列中進行插入。初始時，有序序列的長度為1。

給定序列 [9 , 20 , 13 , 10 , 12 ] 。初始狀態如下：

?分成的兩個序列如下：

也就是說，此時我們講數組當中的第一個元素9當作有序元素。
第一次插入：將20和9做比較，20>9，順序沒有問題。不動。

第二次插入：將13與20比較，13<20，此時20就要先到13的位置。再跟9比較，13>9，那么此時
將13插入到9后面

第三次插入，將10和20比較，10<20，20去10的位置，再將10和13比較，10<13，則13也往下移動，再將10和9比較，10>9，則將10插入到9的后面

第四次插入：將12和20比較，12 <20，20后移，再將12和13比較，12<13，13后移，再將12和10比較，12 > 10,將12插入到10的后面

1.2復雜度

在排序前元素已經是按需求有序了，每趟只需與前面的有序元素序列的最后一個元素進行比較，總的排序碼比較次數為n-1，元素移動次數為0。時間復雜度為 O(n);
而在最差的情況下，及第i趟時第i個元素必須與前面i個元素都做排序碼的比較，并且每做一次就叫就要做一次數據移動，此時的時間復雜度為O(n^2) ；所以直接插入排序的時間復雜度為O(n^2)?插入排序不適合對大量數據進行排序應用，但排序數量級小于千時插入排序的效率還不錯，可以考慮使用。插入排序在STL的sort算法和stdlib的qsort算法中，都將插入排序作為快速排序的補充，用于少量元素的排序（通常為8個或以下）。直接插入排序采用就地排序，空間復雜度為O（1）

1.3穩定性

插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素。如果碰見一個和插入元素相等的，那么將會把待插入元素放在相等元素的后面。所以，相等元素的相對的前后順序沒有改變，所以插入排序是穩定的

1.4代碼演示

#include<stdio.h>
#include<stdlib.h>
/*
直接插入排序：是就地排序，是穩定的，時間復雜度：O（n^2） 
*/ 
int a[105]; 
int n;
int main()
{int t;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}//認為：a[1] 是有序區域，a[2---n]是亂序區for(int i=2;i<=n;i++){t=a[i];int j;for(j=i-1;j>=1;j--){if(a[j]>t){a[j+1]=a[j];} else{break;}}a[j+1]=t;} for(int i=1;i<=n;i++){printf("%d ",a[i]);}return 0;
}

2.折半插入排序

折半插入排序是一種插入排序算法，通過不斷地將數據元素插入到合適的位置進行排序，在尋找插入點時采用了折半查找

2.1基本思想

折半插入排序的基本思想是：順序地把待排序的序列中的各個元素按其關鍵字的大小，通過折半查找插入到已排序的序列的適當位置。
從名字就能看出來，運用了二分查找的插入排序。在上面標準的插入排序算法中，我們會將待插入關鍵字 key = arr[i] ，然后在數組 [0，i - 1] 的范圍內查找待插入關鍵字 key 的正確位置，這里的查找操作的時間復雜度為O(n)量級。但是如果使用二分查找在數組 arr 的 [0,i - 1] 的范圍內查找關鍵字 key ，那么就可以將查找操作的時間復雜度降到O(logn)量級

2.2性能

折半查找只是減少了比較次數，但是元素的移動次數不變。折半插入排序平均時間復雜度O(n^2)；空間復雜度為O(1)；是穩定的排序算法

3.2-路插入排序算法

二路插入排序算法是在折半排序的基礎上對其進行了改進，減少其在排序過程中移動記錄的次數從而提高效率。
具體實現思路為：另外設置一個同存儲記錄的數組大小相同的數組 d，將無序表中第一個記錄添加進d[0]的位置上，然后從無序表中第二個記錄開始，同 d[0] 作比較：如果該值比d[0] 大，則添加到其右側；反之添加到其左側。其實就是對于環形數組的插入

4.希爾排序

希爾排序也是一種插入排序，它是簡單插入排序經過改進之后的一個更高效的版本，也稱為縮小增量排序

4.1基本思想

希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止

簡單插入排序很循規蹈矩，不管數組分布是怎么樣的，依然一步一步的對元素進行比較，移動，插入，比如[5,4,3,2,1,0]這種倒序序列，數組末端的0要回到首位置很是費勁，比較和移動元素均需n-1次。而希爾排序在數組中采用跳躍式分組的策略，通過某個增量將數組元素劃分為若干組，然后分組進行插入排序，隨后逐步縮小增量，繼續按組進行插入排序操作，直至增量為1。希爾排序通過這種策略使得整個數組在初始階段達到從宏觀上看基本有序，小的基本在前，大的基本在后。然后縮小增量，到增量為1時，其實多數情況下只需微調即可，不會涉及過多的數據移動。
我們來看下希爾排序的基本步驟，在此我們選擇增量gap=length/2，縮小增量繼續以gap =gap/2的方式，這種增量選擇我們可以用一個序列來表示，{n/2,(n/2)/2...1}，稱為增量序列。希爾排序的增量序列的選擇與證明是個數學難題，我們選擇的這個增量序列是比較常用的，也是希爾建議的增量，稱為希爾增量，但其實這個增量序列不是最優的。此處我們做示例使用希爾增量

原始數組以相同的顏色為一組

初始增量gap=length/2=5，意味著整個數組被分為5組，[8,3],[9,5],[1,4],[7,6],[2,0]。

然后我們對這5組分別進行直接插入排序，結果就變成

可以看見例如3，5，6這些小元素就在前面了，然后縮小增量gap = 5/2 = 2，將數組分成兩組

?對以上的兩組再分別進行直接插入排序，結果如下。此時整個數組的有序程度就更近一步了

?再縮小增量，gap=2/2=1.此時整個數組為1組。[0,2,1,4,3,5,7,6,9,8]

?此時，只需要對以上數列簡單微調。無需大量的移動操作即可完成整個數組的排序

4.2?性能

希爾排序中對于增量序列的選擇十分重要，直接影響到希爾排序的性能。我們上面選擇的增量序列{n/2,(n/2)/2...1}(希爾增量)，其最壞時間復雜度依然為O(n2)。這是為什么呢？
到底什么地方出了問題呢？我們再來看一個壞的例子，假設這是我們的初始序列，如果用shell的增量序列我們會一開始怎么做呢？這一共有16個數字

我們一開始就做8間隔的排序，8間隔的排序我們就從1開始，然后往后數7個數字，就是排1和5，發現本來就是有序的，什么都不用動，然后下一個，就是9和13，也是有序的，2和6，還是有序的，10和14還是有序的，繼續往后看，就會發現，我做了一個8間隔的排序，結果哪個元素都沒有動，大家保持原樣的走下來了，下一步我要做4間隔的，結果還是全部都是有序的。
結果這趟白跑了，2間隔的排序，你應該猜到結果了，還是什么都沒干，最后要達到有序，還是得靠我們1間隔的排序。結果這趟白跑了，2間隔的排序，你應該猜到結果了，還是什么都沒干，最后要達到有序，還是得靠我們1間隔的排序。所以這其實是一個讓人非常囧的情況，就是前面我白做了3趟排序，然后最后還是跟原始的插入排序一樣，還不如一開始我就直接做原始的插入排序，那到底什么地方出了問題呢？我們通過仔細的分析會發現因為它的增量元素不互質，8是4的倍數，4是2的倍數，2是1的倍數，那么小的增量就有可能在后面的排序里面根本不起作用

4.3Hibbard增量序列

4.4更多的增量序列

4.5代碼演示

#include<stdio.h>
#include<stdlib.h>
/*
希爾排序：取希爾增量序列時： 是就地排序，不是穩定的，時間復雜度：O（n^2）
*/ 
int a[105]; 
int n;
int main()
{int t;scanf("%d",&n);int k=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int d=n/2;d>=1;d=d/2)  {k++;//計算趟數 //以增量d分組，對每組進行直接插入排序for(int i=1+d;i<=n;i++){t=a[i];int j;for(j=i-d;j>=1;j=j-d){if(a[j]>t){a[j+d]=a[j];}else{break;}}a[j+d]=t;	} printf("第%d趟，增量為%d,排好的結果：",k,d);for(int i=1;i<=n;i++){printf("%d ",a[i]);}printf("\n");} return 0;
}

三.交換排序

1.冒泡排序

1.1算法思想

?第二步，比較 5 和 4，5 > 4，交換 5 和 4 的位置：

?第三步：比較 5 和 2 ，5 > 2，交換 5 和 2 的位置：

?第四步：比較 5 和 8 ，5 < 8 ，不交換

?第五步：比較 8 和 4 ， 8 > 4，交換 8 和 4 ：

此刻我們獲得數組當中最大的元素 8 ，使用橘黃色進行標記：
第一輪冒泡結束，最大的元素8到了最后，然后對于前面5個元素，進行第二輪冒泡最終結果：

事實上第二階段結束，整個數組已經有序了，但是對于冒泡排序而言并不知道，她還需要通過第三階段的比較操作進行判斷。
對于冒泡排序算法而言，她是通過判斷整個第三階段的比較過程中是否發生了交換來確定數組是否有序的，顯然上面的過程中沒有交換操作，冒泡排序也就知道了數組有序，整個算法執行結束

1.2關于冒泡的優化

基本的冒泡排序的實現方式，就是兩個for循環，持續比較和交換。這種實現方式有一個明顯的弊端，就是不論數組是否有序，兩層 for 循環都要執行一遍，而我們是希望數組有序的時候，僅進行一輪判斷，或者一輪都不進行（當然不判斷，排序算法是不能知道數組是否有序的）

一次優化

這里我們增加了一個標識數組是否有序 ，當冒泡排序過程中沒有交換操作時， swapped =false ，也意味著數組有序；否則數組無序繼續進行冒泡排序。不要小看這個變量，因為這個變量，當數組有序的時候，冒泡排序的時間復雜度將降至?(因為其只需要執行一遍內層的 for 循環就可以結束冒
泡排序)，沒有這個變量，數組有序也需要的時間復雜度

二次優化
一次優化是為了避免數組有序的情況下，繼續進行判斷操作的。那么二次優化又為了什么呢？
我們看下面的例子

經過一次冒泡后，我們會注意到一個問題，但是我們注意到，數組數組中的 [5,6,8] 本身已經有序，而對于有序的部分進行比較是沒有意義的，相當于在白白浪費資源，有沒有什么辦法減少這樣的比較次數呢？換句話說，是否能夠確定出已經有序部分和無序部分的邊界呢？
答案當然是肯定的，這個邊界就是第一趟冒泡排序的過程中最后一次發生交換的位置 j ：也就是1 和 4 發生交換之后，4 和 5 沒有發生交換，此時 1 之后的元素為有序。

第一步：4 和 2比較，4 > 2 ，交換 4 和 2 ，將 LastSwappedIndex = 0 ；

第二步：4 和 1 比較，4 > 1，交換 4 和 1， LastSwappedIndex = 1 ；
第三步：比較 4 和 5 ， 4 < 5，不交換， lastSwappedIndex 也不更新;
第四步：比較 5 和 6 ，不交換， lastSwappedIndex 也不更新;
第五步：比較 6 和 8 ，不交換， lastSwappedIndex 也不更新;
第一趟冒泡排序結束了，這里似乎看不出和之前有什么區別，但是來看第二趟冒泡排序就不一樣了，此時 j 的 取值將從 j = 0 到 j = lastSwappedIndex ，第一步：比較 2 和 1 ，2 > 1，交換， lastSwappedIndex = 0 ，并且第二趟冒泡也就結束了，也就說我們節省了 從 2 到 6的比較操作；
最后再來一趟冒泡排序，發現沒有任何交換，所以冒泡排序結束。
相比于一次優化的實現方式，二次優化的實現方式進一步減少了不必要的執行次數，兩種優化后的實現方式需要冒泡排序的趟數是一樣的，本質上沒有什么區別。所以即使對于一個有序的數組，兩種方式的時間復雜度都是O（n）

1.3復雜度分析

時間復雜度：
最壞情況下（數組逆序）：
當 i == 0 的時候，j 的取值范圍是從 0 到 n -1，內循環的執行判斷和交換操作 n - 1 次；當 i == 1的時候，j 的取值范圍是從 0 到 n -2，內循環的執行判斷和交換操作 n - 2 次；以此類推......當 i 取最大值n - 2 時，j 的取值為 1，內循環的執行判斷操作 1 次；所以，整體內循環的判斷語句執行次數就是：1 +2 + 3 + ... + (n - 2) + (n - 1) 。則最壞情況下的時間復雜度為O（n^2）量級。
最好情況下（數組有序）：
當 i == 0 的時候， swapped = false ，j 的取值范圍是從 0 到 n -1，內循環的執行判斷操作 n -1次，但是沒有發生交換操作，冒泡排序算法直到數組已經有序，所以執行結束。則最好情況下的時間復雜度為O（n）。

空間復雜度：
冒泡排序沒有使用任何額外的空間，空間復雜度為 O（1），是典型的原地排序算法

穩定性分析：
我們可以發現，兩個 4 的相對位置沒有發生變化，也就是說冒泡排序是穩定的。但這僅相當于實驗驗證，而在理論上冒泡排序為什么是穩定的呢？
本質原因在于冒泡排序比較和交換的是兩個相鄰元素，對于鍵值相同的關鍵字是不交換位置的，所以排序前后鍵值相同的關鍵字的相對位置才保持不變的

1.4如何用兩個棧實現冒泡

對于這個問題本身，你可能會覺得沒有任何意義，但是當你去努力實現的時候，就會發現，你對于棧和冒泡排序的理解有了新的見解。
問題本身不難理解，就是利用兩個棧，然后每一次選擇出數組中最大的元素，并存入數組對應的位置。但是當你自己去實現時，還是會發現好多問題，比如如何互換著使用兩個棧？如何對棧中相鄰的兩個元素比較大小，并交換位置？
下面是參考的思路：
給定兩個棧 s1 和 s2 ，以及一個長度為 n 的數組 arr :
1、將數組 arr 中的所有元素壓入棧 s1 當中；
2、執行?for 循環 n 次（每一次選擇出一個最大的元素）：
1. 情況一： s1 不為空， s2 為空，則嘗試將棧 s1 當中的所有元素壓入棧 s2 ，并保證 s2的棧頂元素為最大值；當 s1 為空時， s2 中的棧頂元素即為棧中元素的最大值，插入數組相應位置。
2. 情況二： s2 不為空， s1 為空，則嘗試將棧 s2 當中的所有元素壓入棧 s1 ，并保證 s1的棧頂元素為最大值；當 s2 為空時， s1 中的棧頂元素即為棧中元素的最大值，插入數組相應位置。

1.5詳細解析

初始時兩個棧 s1 和 s2 都為空棧，數組 arr[] = [5,1,4,2,8] 。
第一步：將數組 arr 中的所有元素都壓入棧 s1 當中：

第二步：棧 s2 為空，直接將 s1 的棧頂元素 8 壓入棧 s2?

第三步：棧 s1 不為空，嘗試將 s1 的棧頂元素 2 壓入棧 s2 ，但是此時 s2 的棧頂元素 8 >2，所以利用一個臨時變量 tmp 交換兩個元素在棧中的位置，先將 s2 的棧頂 8 保存到 tmp 并彈出，然后壓入元素 2 ，最后再將8重新入棧。(其實就是交換操作)

?第四步：棧 s1 不為空，同第三步一樣將 s1 的棧頂元素壓入棧 s2 當中：

第五步：棧 s1 不為空，同上將 s1 的棧頂元素 1 壓入棧 s2 當中：?

第六步：棧 s1 不為空，同上將 s1 的棧頂元素 5 壓入棧 s2 當中：?

之后的過程和前面講的類似，將棧 s2 中的元素壓入棧 s1 當中，并找到次大元素 5 ，以此類推，實現對數組的冒泡排序

1.6代碼演示

#include<stdio.h>
#include<stdlib.h>
#define maxx 100
/*所謂交換,是指根據序列中兩個關鍵字比較的結果來對換這兩個關鍵字在序列中的位置。*/
int a[maxx],n,t;
int v;//標記 
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}//冒泡排序//外層循環控制 排序的趟數 n個元素排序需要循環n-1次 【1】for(int i=1;i<=n-1;i++) {v=0;//內層循環控制比較的次數 n個元素第i趟比較n-i次 【2】for(int j=1;j<n-i+1;j++) {//比較相鄰的元素大小 目的：將最大的元素選出到移動到最后 if(a[j]>a[j+1]){v=1;t = a[j];a[j] = a[j+1];a[j+1] = t;}}if(v==0)//v仍然等0，說明沒交換，說明完全有序 {break;}}for(int i=1;i<=n;i++){printf("%d ",a[i]);}return 0;
}

2.快速排序

2.1算法思想

快速排序首先選一個基準（你也可以認為是要放到排序后數組正確位置的元素）pivot，然后將數組按照選取的基準 pivot 進行劃分。而選取 pivot 的方式又有很多種，所以快速排序具有很多版本。
總是選擇第一個元素作為基準 pivot；
總是選擇最后一個元素作為基準；（以這個舉例）
隨機的選擇一個元素作為基準；
選擇最中間的元素作為基準；
快速排序的關鍵是劃分 partion() 。每一趟劃分，我們就可以將作為 pivot 的值 x 放到排序數組的正確位置，并且將所有比?x 小的放到 x 的左邊，所有比?x 大的元素放到 x 的右邊。而且劃分操作的時間復雜度是線性，即O（n）量級！
為了講解快速排序并驗證其穩定性，我們用下面的數組進行說明（其中兩個4分別用不同的顏色標注）：

首先選擇數組當中的最后一個位置元素 7 作為 pivot：然后就是執行第一趟快速排序
第一步：設置一個指針 i = -1 （初始化為 -1，用于找到 pivot 的正確位置），設置一個遍歷數組的指針 j = 0 ，用于遍歷從 0 到 pivot 的前一個元素 4 （即兩條豎線之間的元素，從而將 7 放到排序后數組的正確位置）：

第二步：比較 j 當前指向的元素 1 和 7 ，1 <= 7 ；指針 i++ ，即 i = 0 ，交換 arr[i] 和arr[j] ，即 交換 arr[0] 和 arr[0] （數組本身并無變化） ；便利然后指針 j 向右移動：

第三步：比較當前 j 指向的元素 8 和 7 （pivot），8 > 7；什么都不做；然后指針 j 向右移動：

第四步：比較當前 j 指向的元素 3 和 7 ，3 <= 7；指針 i++ ，即 i = 1 ，交換 arr[i] 和arr[j] ，即 交換 arr[1] = 8 和 arr[2] = 3 ；然后指針 j 向右移動：

第五步：比較當前 j 指向的元素 9 和 7 ，9 > 7；什么都不做；然后指針 j 向右移動：

第六步：比較當前 j 指向的元素 4 ，4 <= 7；指針 i++ ，即 i = 2 ，交換 arr[i] 和arr[j] ，即交換 arr[2] = 8 和 arr[4] = 4 ；然后指針 j 向右移動：

第七步：比較當前 j 指向的元素 5 和 7 ，5 <= 7；指針 i++ ，即 i = 3 ，交換 arr[i] 和arr[j] ，即交換 arr[3] = 9 和 arr[5] = 5 ；然后指針 j 向右移動：

第八步：比較當前 j 指向的元素 4 和 7 ，4 <= 7；指針 i++ ，即 i = 4 ，交換 arr[i] 和arr[j] ，即交換 arr[4] = 8 和 arr[6] = 4 ；然后指針 j 向右移動：

?第九步：此時遍歷結束，交換 arr[i+1] 和 arr[high] = pivot ，即交換 9 和 7

此時第一趟快速排序結束啦，我們確定了最開始選擇的 pivot 的正確位置。
接下就是分別對 7 左側比?7 小的元素 [1,3,4,5,4] ，與右側比?7 大的元素進行快速排序，過程和第一趟排序過程一樣
這里就會有一個問題，一趟快速排序結束了。就是將數組按照pivot分成了小于等于pivot的一組和大于pivot的一組，可是分治的明顯么？好像不明顯。
前面提到快速排序和歸并排序一樣均屬于分治算法，而我之前在寫歸并排序時提到過，分治與遞歸就是?個孿生兄弟，提到了分治，怎能缺少遞歸呢？
遞歸三要素中最核心的就是確定一個函數的功能，而我們經過上面對一趟快速排序的介紹，可以發現，之后的每一趟快速排序事實上和第一趟是一樣的，也就意味著反復調用同一個函數存在，即快速排序的過程中蘊含了遞歸思想，這也是分治的個佐證。
但是我們也可以有更清晰的解釋，且看下圖：

首先根據原始數組 [1,8,3,9,4,5,4,7] ，將數組劃分為小于等于 7 的數組 [1,3,4,5,4] 和[8,9] ，然后將 [1,3,4,5,4] 根據 4 劃分為 [1,3,4] 和 [5] ；將 [1,3,4] 根據 4 劃分為[1,3] ；將 [1,3] 根據 3 劃分為 [1] ；將 [8,9] 根據 9 劃分為 [8] ；這個過程不就是二分嗎？

的確如此，只不過對于這個數組而言選擇最末尾的元素作為 pivot 得到的樹的高度并不是我們期望的logn = log8 = 3 ，而是 4 說到這里，我們順帶說一下快速排序的缺點，對于一個有序數組 [1,3,4,4,5,7,8,9] 而言，如果每次選擇最后一個元素作為 pivot ，就會得到下面一幅圖：

而這時樹的高度變成了n ，也就意味著快速排序退化成了一顆單鏈，這不是我們希望看到的。但是我們每一次選擇最中間的元素作為 pivot ，又會怎么樣呢？
如果將數組 [1,8,3,9,4,5,4,7] 重新調整順序，使得快速排序的的分治過程如上圖所示？看著圖就能寫出來了，當然答案可能有很多個，最簡單的一個就是 [1,4,3,5,8,9,7,4] 。

2.2復雜度分析

快速排序的時間通常表示為：T(n) = T(k) + T(n - k + 1) + n
其中 T(k) 和 T(n - k + 1) 分別表示遞歸調用，而最后一項n表示將最后一個元素作為pivot進行劃分 的處理過程，k 表示比?pivot 小的元素的數目。
而快速排序的時間復雜度取決于輸入的數組和劃分策略，所以需要從三個方面分析：

最壞情況：
最后情況就是我們每一次選擇最大的元素或者最小的元素作為 pivot 。以我們上面講快速排序選擇做末尾的元素作為 pivot，最壞情況就是輸入的待排序數組為有序數組（以升序為例），此時 k = n -1 ，那么：T(n) = T(n - 1) + T(0) + n ,即T(n) = T(n-1)+n ;所以最壞情況下的時間復雜度為O(n^2) 量級。不理解推導沒關系，設對有序數組 [1,3,4,4,5,7,8,9] 進行快速排序，每次選擇最末尾的元素作為 pivot，那么就會得到下圖所示的情況：

也就說需要選擇 n個 pivot，并且以每一個 pivot 進行劃分需要O(n)的時間，那么總的時間就是O(n^2)量級

最好情況：
當劃分過程中每一次都能選擇最中間的元素作為基準 pivot ，那么快速排序的時間復雜度就等于：T(n) = T(n/2)+T(n/2)+n 其中T(n)表示快速排序的時間復雜度，T(n/2) 表示劃分出的兩個子數組排好序所用的時間， n表示將最后一個元素作為pivot進行劃分函數的執行時間。
根據主定理，快速排序最好情況下的時間復雜度為 O(nlogn).
當然我們也可以換一個角度來算，比如對數組 [1,8,3,9,4,5,4,7] 而言，我們希望得到的是下面一幅圖：

這個樹的高度就是 O(logn)，也就是選擇 pivot 需要O(logn) 次，而根據每一個 pivot 我們需要 O(n)的時間執行劃分函數，所以總的時間復雜度為O(nlogn)量級。

空間復雜度分析：
快速排序的實現中，我們僅使用了一個臨時變量用于交換操作，也就是其空間復雜度為O(1)，所以快速排序也是一個原地排序算法。
穩定性分析：
快速排序的劃分階段會進行交換操作，而這種交換操作會破壞原始數組中元素之間的相對位置，也就意味著，快速排序是一個不穩定的排序算法。當然所有的排序算法都可以變得穩定

2.3快速排序的穩定性從哪里來

快速排序是不穩定的。這個論述在標準的教科書上已經提了很多次，也沒有什么疑問。
但是，可否通過改進的方法將其變成一個穩定的排序算法呢？
快速排序的核心過程是 Partition 函數，這個函數的作用是選擇一個基準，使比之小（或等于）的數都在結果列表中處于其左邊，比之大的數都在結果列表中處于其右邊。我們發現，快速排序不穩定性的根源就來自于此。比如這個例子：
【1，4，2-1，3，6，2-2，5，2-3】
列表中出現了三個2，那么我們如果選擇中間的2（綠色）作為基準，則第?次Partition結束的列表成為
【1，2-1，2-3，2-2，4，3，6，5】
或者
【1，2-3，2-1，2-2，4，3，6，5】
可見，黃色和藍色的2都被分在了綠色2的左邊或者右邊，明顯三個2的相對順序變化了。
結論：如果一個數字在待排序的列表中出現三次或以上，而這個數字在列表中出現的（非首次和末次）一次被選為基準（pivot），則結果肯定是不穩定的。
因此，通過更改比較時>=符號為>符號是沒有意義的，因為不穩定的根源在于基準的選取。
如果要得到穩定的快速排序，必須在選取基準時避免這種情況，而且在交換元素時要小心不要打亂相同元素的相對順序。一種可選的做法是先記錄相同元素的相對位置，再進行排序。這需要額外的空間開銷

2.4代碼演示

#include<stdio.h>
#include<stdlib.h>
/*交換排序：基于數據交換的排序
1.冒泡排序：是就地排序， 是穩定的，時間復雜度 O（n^2） 
2.快速排序：---遞歸: 是就地排序，不穩定，時間復雜度O(nlogn) ------待排序的數組已經保持需要的順序了，容易退化成O(n^2) 
每一趟：先選一個標準（基準數），按照基準數進行劃分，把比基準數小的交換到他前面，
把比基準數大的交換到他后面 
基準數怎么選：對區間(l,r) 
（1）選排序區間的第一個數--a[l]------為例 
（2）選排序區間的最后一個數--a[r] 
*/ 
void QuickSort(int a[],int l,int r)
{//選排序區間的第一個數--a[l]做基準數if(l>=r){return;} int x=a[l];int i=l;int j=r; while(i<j){//先 從后往前，找一個小于基準數小的數，放到i位置 while(i<j&&a[j]>x)j--; if(i<j){a[i]=a[j];i++;} //再從前往后，找一個小于基準數大的數，放到j位置while(i<j&&a[i]<x)i++; if(i<j){a[j]=a[i];j--;} }a[i]=x;QuickSort(a,l,i-1); QuickSort(a,i+1,r);
}
int main()
{int a[105]; int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}//快速排序QuickSort(a,1,n); for(int i=1;i<=n;i++){printf("%d ",a[i]);}printf("\n");return 0;
}

四.歸并和計數排序

1.歸并排序

1.1算法思想

歸并排序和之前的冒泡排序、插入排序和選擇排序不同，其蘊含了一種分治的思想。
話不都說，我們還是以數組 arr = [5,1,4,2,8,4] 為例進行一趟歸并排序。

第一步：計算數組的中間元素m = (l + r)/2 = 2 ，然后將數組分成[l,m]]和[m+1,r]兩個區間，即[0,2]與[3,5]兩個子數組，這一步屬于「分」的過程

第二步：計算分出來的子數組[0,2]]的中間元素，m = (l + r)/2 = 1 ，將數組分成了[0,1]以及[2] 兩個子數組，這一同樣是「分」的過程，但同時也應該注意到，這一步和第一步的操作過程是一致的，也就說第一步和第二步是同一個功能，所以最終你會在代碼中看到遞歸實現，后面會專門講歸并排序所蘊含的遞歸思想

第三步：將上一步分出的子數組 [0,1] 再進行拆分，m = 0 , 將數組分成了 [0] 和 [1]，只包含一個元素。?

第四步：將 arr[0] 和 arr[1] 進行合并，因為上一步得到的兩個數組不可再分了，已經有序，所以進行合并。這一步事實上也是 「治」的過程，所謂治就是真正進行排序的過程，因為通過這一步元素 5和 1 的順序將被改變

之后的每一步都是如此，我們在下圖中將每一步用紅色數字標注了出來：

分治和遞歸就像一對好基友，永遠不分離，為了看到歸并排序的遞歸過程，我們先看一下歸并排序的實現。
這里的遞歸過程如此曲折，事實上沒有什么可擔心的，你將代碼中的 mergeSort(arr,l,r) 理解為「分」和「遞」，而將 merge(arr,l,m,r) 理解為 「治」和「歸」，心中就會豁然開朗，遞歸與分治就是孿生兄弟。

1.2復雜度分析

時間復雜度：
歸并排序（二路歸并）方法就是把一個包含 n 個數的數組，折半拆分為兩個子數組（二路），然后再將這兩個子數組再分，一直分下去，直到分為n個長度為1的元素。然后兩兩按大小歸并。如此反復，直到最后形成包含 n 個數的一個有序數組。
歸并排序總時間 = 拆分時間 + 子數組排好序時間 + 合并時間
無論每個數組有多少個數都是折半拆分，也就是代碼中的 int m = (left + right) / 2;?
所以拆分時間就常數O（1）級別，可以忽略不計。則：歸并排序總時間 = 子數組排序時間 + 合并時間
空間復雜度：
在合并的時候，我們使用了存儲待合并的兩個數組元素的空間，這個數組大小依次開辟的就是1，2，4，8，...，n/2，但是開辟了兩個，所以可能開辟的空間大小為 2，4，8，......，n，歸并排序的空間復雜度為O(n)量級。與插入排序，冒泡排序，還有選擇排序相比，你也可以將歸并排序理解為空間換時間的有效例證。歸并排序也就不是一個原地排序算法了，原地排序算法的空間復雜度為O(1).
穩定性分析：
這幅圖中，可以看到歸并排序是穩定的排序算法，排序前后，數組中兩個4的相對位置沒有發生變化。歸并排序穩定的根本原因在合并的時候對值相同的兩個關鍵字不存在交換的可能性。

1.3代碼演示

#include<stdio.h>
#include<stdlib.h>
#define maxx 100
void merge(int a[],int l,int mid,int r)
{//l~mid//mid+1~rint t[maxx];int k=0;//t數組的下標 int i=l;int j=mid+1;while(i<=mid&&j<=r){if(a[i]<=a[j]){t[k]=a[i]; k++;i++;}else{t[k]=a[j];k++;j++;}}while(i<=mid){t[k]=a[i]; k++;i++;}while(j<=r){t[k]=a[j]; k++;j++;}for(int i=0;i<k;i++){a[l+i]=t[i];}
}void merge_sort(int a[],int l,int r)
{int mid;if(l<r){mid=(l+r)/2;//l~midmerge_sort(a,l,mid);//mid+1~rmerge_sort(a,mid+1,r);merge(a,l,mid,r);}}
int main()
{int n;//元素個數int a[maxx];// scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}merge_sort(a,1,n);for(int i=1;i<=n;i++){printf("%d ",a[i]);}printf("\n");return 0;
}

2.計數排序

計數排序是一種針對于特定范圍之間的整數進行排序的算法。它通過統計給定數組中不同元素的數量（類似于哈希映射），然后對映射后的數組進行排序輸出即可。（計數排序在某些情況下比快速排序還要快）

2.1算法思想

我們以數組 [1,4,1,2,5,2,4,1,8] 為例進行說明

第一步：建立一個初始化為 0 ，長度為 9 (原始數組中的最大值 8 加 1) 的數組 count[] :

?

第二步：遍歷數組 [1,4,1,2,5,2,4,1,8] ，訪問第一個元素 1 ，然后將數組 count[] 中下標為 1 的元素加 1，表示當前 1 出現了一次，即 count[1] = 1 ;

第三步：訪問數組 [1,4,1,2,5,2,4,1,8] 的第二個元素 4 ，然后將數組 count[] 中下標為 4的元素加 1 ，表示當前訪問的元素 4 當前出現了 1 次，即 count[4] = 1 ;

第四步：訪問數組 [1,4,1,2,5,2,4,1,8] 的第三個元素 1 ，然后將數組 count[] 中下標為 1 的元素加 1，即 count[1] = 2 ，表示當前 1 出現了 2 次：

第五步：訪問數組 [1,4,1,2,5,2,4,1,8] 的第四個元素 2 ，然后將數組 count[] 中下標為 2 的元素加 1，即 count[2] = 1 ，表示當前 2 出現了 1 次：

第六步：訪問數組 [1,4,1,2,5,2,4,1,8] 的第五個元素 5 ，然后將數組 count[] 中下標為 5的元素加 1，即 count[5] = 1 ，表示當前 5 出現了 1 次：

第七步：訪問數組 [1,4,1,2,5,2,4,1,8] 的第六個元素 2 ，然后將數組 count[] 中下標為 2的元素加 1，即 count[2] = 2 ，表示當前 2 出現了 2 次：

第八步：訪問數組 [1,4,1,2,5,2,4,1,8] 的第七個元素 4 ，然后將數組 count[] 中下標為 4的元素加 1，即 count[4] = 2 ，表示當前 4 出現了 2 次：

第九步：訪問數組 [1,4,1,2,5,2,4,1,8] 的第八個元素 1 ，然后將數組 count[] 中下標為 1的元素加 1，即 count[1] = 3 ，表示當前 1 出現了 3 次：

第十步：訪問數組 [1,4,1,2,5,2,4,1,8] 的第九個元素 8 ，然后將數組 count[] 中下標為 8的元素加 1，即 count[8] = 1 ，表示當前 8 出現了 1 次：

此時遍歷數組 [1,4,1,2,5,2,4,1,8] 結束，我們得到了一個 count[] 數組，而只要得到了這個 count[] 數組，我們的排序算法就相當于結束了，接下來的就只是輸出了

2.2穩定性

如果不考慮計數排序的穩定性，我們按照數組 count[] 中對應下標的出現次數直接輸出即可：
為了保證計數排序的穩定性，我們又該如何做呢？
先不考慮這么復雜，但是從宏觀的角度來看，我們的目的就是找到待排序數組中每一個元素在排序后數組當中的正確位置。首先看一下 count[] 數組本身， 數組中的 0 對于我們的輸出沒有任何影
響，所以我們可以考慮將其直接去掉：

?那么此時的我們就可根據去掉之后的數組得到排序后數組的一個輪廓圖：

但是這樣我們并不知道相同的數字在對應原始數組 arr[] 中的哪一個元素，就相當于直接輸出，而沒有考慮元素的相對順序；但是對這個過程的理解有助于我們接下來理解穩定性的處理過程。
我們看到，數組 count[] 中的每一個值表示它所對應的下標在排序后數組的出現次數，那么我們遍歷數組（下標從 1 開始），并對數組 count[] 中的每一個元素執行count[i] = count[i] +count[i-1] 會得到什么呢？?

此時得到新的 count[] 將表示他們的位置信息，比如 3 表示它的下標 1 一定出現在前 3 的位置；而緊接其后 5 則表示下標 2 出現在第 4 和第 5 個位置；下標為 3 的 count[3] = 5 ，其與前面count[2] 值相同，兩者之差也就表示其出現次數，0 次，所以不占位置；下標為 4 的位置值為 7 ，則表示下標 4 出現在第 6 和 7 的位置，依次類推，你也可以對新的 count[] 數組中的每一個元素做出解釋。
但我們怎么可能停留在這里呢？
有了這個新的 count[] 數組，我們如何得到元素數組 arr[] 在排序后的輸出數組 output[]中的正確位置呢？
回答了這個問題，穩定的計數排序也就徹底理解了
第一步：從后向前遍歷，具體為什么是從后向前，看完了你就會明白了！首先是 i = n-1 = 8，然后計算出 arr[i] = arr[8] = 8 在排序后數組的正確位置 count[arr[i]] - 1 = count[8] -1 = 8 ，即排序后arr[8] 的正確位置為 8 ，然后將 arr[8] 賦值給 output[8] = 8 ，但是count[arr[8]] = count[8] 減 1 ：

第二步： i = n - 2 = 7 ，然后計算 arr[7] = 1 在排序后數組的正確位置 count[arr[7]] - 1 = count[1] - 1 = 2 ，即最后一個 1 在排序后的正確位置下標為 2 ，然后將 count[arr[7]]的值減 1 。這里為什么要減 1 ，因為我們已經找到了最后一個 1 的正確位置，目前就剩余兩個 1 沒有找到正確位置。

?依次類推，我們就可以得到arr[]中每一個元素在排序后的正確位置

這就是穩定的計數排序，那我們再來回答一下為什么從后向前遍歷新的 count[] 數組？
因為只有這樣才能保證計數排序的穩定性！比如原始數組 arr[] 中 3 個 1 的在排序后的相對位置就沒有發生變化，依舊保持：
可是問題又來了，如果我們的數組變成了 arr[] = {-1,4,1,-2,5,-2,4,-1,8} ，上面介紹的計數排序的實現方式不就出現了問題嗎？因為數組下標也沒有負數的情況呀！很簡單，將最小元素映射到下標為0的位置。其他元素依次映射。
我們只需要找到數組 arr[] = {-1,4,1,-2,5,-2,4,-1,8} 中的最小值 min = -2 ，以及最大值 max = 8，然后開辟一個大小為 max - min + 1 的 count[] 數組，統計出數組當中每一個元素出現的次數即可，就像下面這樣：?

其中數組 arr[] 的最小值 min = -2 ， -2 被映射到了 count[] 數組下標為 0 的位置，原數組中包含 2 個 -2 ，所以 count[0] = 2 ；原數組 arr[] 當中有 3 個 -1 ，其中 -1 - (-2) = 1 ，也就說 -1映射到了 count[] 數組下表為 1 的位置，所以 count[1] = 3?

2.3復雜度分析

時間復雜度：
在整個代碼實現過程中，我們僅僅出現了一層的 for 循環，沒有出現任何 for 循環的嵌套，所以計數排序的時間復雜度為O（n）量級。
空間復雜度：
由于計數排序過程中，我們使用到了一個 max - min + 1 大小的 count[] 數組，所以計數排序的空間復雜度為O（n）量級。
優缺點分析：
1. 如果輸入數據的范圍 range = max - min + 1 不明顯大于要待排序數組的長度 n = arr.length ，則計數排序是相當高效的，比時間復雜度為 的快速和歸并排序都優秀。
2. 計數排序不是基于比較的排序算法，時間復雜度為 ，空間復雜度與數據范圍成正比。
3. 計數排序通常用作另一個排序算法（例如基數排序）的子過程。
4. 計數排序可以使用部分哈希在O（1）的時間內統計數據的頻率。
5. 計數排序適用于負輸入。
6. 計數排序不適用于小數的情況。

3.桶排序

3.1桶排序的思想

其實桶排序重要的是它的思想，而不是具體實現，桶排序從字面的意思上看：
1、若干個桶，說明此類排序將數據放入若干個桶中。
2、每個桶有容量，桶是有一定容積的容器，所以每個桶中可能有多個元素。
3、從整體來看，整個排序更希望桶能夠更勻稱，即既不溢出(太多)又不太少。
那么這些個桶跟排序有什么關系呢？我們先來看桶排序的定義

工作的原理是將數組分到有限數量的桶子里。每個桶子再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排序）。桶排序是鴿巢排序的一種歸納結果。當要被排序的數組內的數值是均勻分配的時候，桶排序使用線性時間（Θ（n））。但桶排序并不是比較排序，他不受到 O(n log n) 下限的影響

?簡單點說：
1、將代排序的序列部分分到若干個桶中，每個桶內的元素再進行個別的排序。
2、時間復雜度最好可能是線性的O（n），桶排序不是基于比較的排序
當然，桶排序是一種用空間換取時間的排序

既然是排序，那么最終的結果肯定是從小到大的，桶排序借助桶的位置完成一次初步的排序——
將待排序元素分別放至各個桶內。
而我們通常根據待排序元素整除的方法將其較為均勻的放至桶中，如 8 5 22 15 28 9 45 42 39 19 27 47 12 這個待排序序列，假設放入桶編號的規則為： n/10 。這樣首先各個元素就可以直接通過整除的方法放至對應桶中。而右側所有桶內數據都比左側的要大

在剛剛放入桶中的時候，各個桶的大小相對可以確定，右側都比左側大，但桶內還是無序的，對各個桶內分別進行排序，再依次按照桶的順序、桶內序列順序得到一個最終排序的序列

3.2關于桶排序的算法分析

上面講了桶排序的具體思想，但是你是不是總覺得心理沒那么踏實呢，這就完了？總覺得怪怪的是吧？
桶排序確實有很多不一樣的地方，無論是算法時間復雜度還是整個算法的流程，都不如啥快排、歸并這些傳統排序來的實在。
桶排序的時間復雜度到底是多少？
我們假設有 n 個待排序數字。分到 m 個桶中，如果分配均勻這樣平均每個桶有 n/m 個元素。首先在這里我鄭重說明一下桶排序的算法時間復雜度有兩部分組成：
1.遍歷處理每個元素，O(n)級別的普通遍歷
2.每個桶內再次排序的時間復雜度總和
對于第一個部分，我想大家都應該理解最后排好序的取值遍歷一趟的O(n);而第二部分咱們可以進行這樣的分析：
如果桶內元素分配較為均勻假設每個桶內部使用的排序算法為快速排序，那么每個桶內的時間復雜度為 (n/m) log(n/m) 。有m個桶，那么時間復雜度為 m * (n/m)log(n/m) = n (log n-log m) .在這里如果到達極限情況 n=m 時。就能確保避免桶內排序，將數值放到桶中不需要再排序達到O(n)的排序效果,當然這種情況屬于計數排序

3.3桶排序適用情況

桶排序并且像常規排序那樣沒有限制，桶排序有相當的限制。因為桶的個數和大小都是我們人為設置的。而每個桶又要避免空桶的情況。所以我們在使用桶排序的時候即需要對待排序數列要求偏均勻，又要要求桶的設計兼顧效率和空間。
桶排序的適用場景非常明了，那就是在數據分布相對比較均勻或者數據跨度范圍并不是很大時，排序的速度還是相當快且簡單的

但是當數據跨度過大時，這個空間消耗就會很大；如果數值的范圍特別大，那么對空間消耗的代價肯定也是不切實際的，所以這個算法還有一定的局限性。同樣，由于時間復雜度為 O(n+m)，如果 m比 n 大太多，則從時間上來說，性能也并不是很好。但是實際上在使用桶排序的過程中，我們會使用類似散列表的方式去實現，這時的空間利用率會高很多，同時時間復雜度會有一定的提升，但是效率還不錯。我們在開發過程中，除了對一些要求特別高并且數據分布較為均勻的情況使用桶排序，還是很少使用桶排序的，所以即使桶排序很簡單、很快，我們也很少使用它。
桶排序更多地被用于一些特定的環境，比如數據范圍較為局限或者有一些特定的要求，比如需要通過哈希映射快速獲取某些值、需要統計每個數的數量。但是這一切都需要確認數據的范圍，如果范圍太大，就需要巧妙地解決這個問題或者使用其他算法了

4.基數排序

與基于比較的排序算法（歸并排序、堆排序、快速排序、冒泡排序、插入排序等等）相比，基于比較的排序算法的時間復雜度最好也就是O（nlogn），而且不能比?O（nlogn）更小了。
計數排序的時間復雜度為O（n）量級，更準確的說，計數排序的時間復雜度為O（n + k），其中k表示待排序元素的取值范圍（最大與最小元素之差加 1 ）。
那么問題來了，當這個元素的的范圍在 1 到 n^2 怎么辦呢？
此時就不能用計數排序了奧，因為這種情況下，計數排序的時間復雜度達到了O(n^2)量級。
比如對數組 [170, 45, 75, 90, 802, 24, 2, 66] 這個而言，數組總共包含 8 個元素，而數組中的最大值和最小值之差為 802 - 2 = 800 ，這種情況下，計數排序就 ”失靈了“ 。
那么有沒有那種排序算法可以在線性時間對這個數組進行排序呢？
答案就是今天要講的基數排序?。基數排序的總體思想就是從待排序數組當中，元素的最低有效位到最高有效位逐位進行比較排序；此外，基數排序使用計數排序作為一個排序的子過程。
下面我們就以數組 [170, 45, 75, 90, 802, 24, 2, 66] ，學習基數排序！

4.1算法思想

數組當中的最大值802為三位數，所以我們在不足三位的數字前面補 0 ，即 [170, 045, 075, 090, 802, 024, 002, 066] 方便后續說明基數排序

第一步：按數組當中元素的最低有效位，個位 [170 ,045 ,075 , 090 ,802 , 024 , 002 , 066 ]，進行計數排序：

?第二步：按數組當中元素的次最低有效位，十位數 ，進行計數排序：

?

?第三步：按數組當中元素的最高有效位，百位，進行計數排序：

?

?這樣我們就完成了基數排序，得到了一個有序數組 [2, 24, 45, 66, 75, 90, 170, 802]

4.2復雜度分析

時間復雜度：
設d表示輸入的數組當中最大值的位數（比如 802，3位，d = 3 ），那么基數排序的時間復雜度就是 O(d x (n+b))，其中n表示數組的長度，而b則是表示一個數的基礎，對十進制而言?b = 10 ；
設K是一個計算機可表示的最大整數，那么d = log以b為底K ；則基數排序整個時間復雜度為O( (n+b) X log以b為底K) 。對于一個較大的數 K，計數排序的這個時間復雜度似乎比基于比較的排序算法都慢，但是事實未必。
假設 K <= n^c取一個最大整數，其中c是一個常量；
那么基數排序的時間復雜度就為 O( c X (n+b) X log以b為底K) ，其中b 和 c都是常數，我們可以忽略不計，那么基數排序的時間復雜度就變成了O( nX log以b為底n) ，但是這依舊不比基于排序算法的最好時間復雜度 O(nlogn)好呀？
可是當我們將這個b取足夠大呢？ b取多少的時候基數排序的時間復雜度才能變成線性呢

當b = n 的時候， ，logn為底n = 1,基數排序的時間復雜度就變成了O(n) ，線性時間復雜度。也就說，當數字用n進制表示的時候，我們就可以對 1 到n^c 范圍之內的數組進行線性排序。對于元素的跨度（范圍）比較大的數組而言，基數排序的運行時間可能比快速排序要好。但是對于基數排序而言，其漸近時間復雜度中隱含了更高的常量因子，并非完全的線性；而快速排序更有效地利用硬件緩存，提高其效率。此外，基數排序使用計數排序作為子過程，計數排序占用額外的空間來對數組進行排序。
但是基數排序解決我們最開始所提出的問題，當數據范圍在 1 到 n^2 時，計數排序的復雜度將變
為O(n^2)量級，而基數排序依舊可以在線性時間進行排序！

空間復雜度：
計數排序使用了額外的空間進行排序，空間復雜度為 O(n)

五.選擇排序（二叉堆）

1.堆

堆是一類基于完全二叉樹的特殊數據結構。通常將堆分為兩種類型： 1、大頂堆（Max Heap）：在大頂堆中，根結點的值必須大于他的孩子結點的值，對于二叉樹中所有子樹都滿足此規律 2、小頂堆（Min Heap）：在小頂堆中，根結點的值必須小于他的孩子結點的值，對于二叉樹中所有子樹都滿足此規律

?小頂堆就是以任意一個結點作為根，其左右孩子都要大于等于該結點的值，所以整顆樹的根結點一定是樹中值最小的結點，而大頂堆正好特性相反

2.二叉堆

二叉堆是滿足下面屬性的一顆二叉樹：

1、二叉堆必定是一顆完全二叉樹。二叉堆的此屬性也決定了他們適合存儲在數組當中。
2、二叉堆要么是小頂堆，要么是大頂堆。小頂二叉堆中的根結點的值是整棵樹中的最小值，而且二叉樹中的所有頂點及其子樹均滿足這一特性。大頂堆與小頂堆類似，大頂堆的根結點的值是整棵樹中的最大值，而且二叉樹中所有結點的值也均大于等于其子樹結點。
由于小頂堆和大頂堆除了在頂點的大小關系上不一致，兩者均是一顆全完二叉樹，下面的所有講解，都以小頂堆為例進行說明，會了小頂堆，大頂堆你自己都能寫出來。

3. 二叉堆的存儲結構

二叉堆是一顆完全二叉樹，一般用數組表示。其中根元素用?arr[0] 表示，而其他結點（第 i個結點的存儲位置）滿足下表中的特性：

數組表示	含義
arr[(i-1)/2]?	第 i 個結點的父結點
arr[2*i + 1]?	第 i 個結點的左孩子結點
arr[2*i + 2]?	第 i 個結點的右孩子結點

二叉堆的這種表示方式和性質其本質上與一顆完全二叉樹自身所具有的特性一一對應

4. 小頂二叉堆常見的操作

獲得元素/根元素：
獲取小頂二叉堆的根元素 getMin() 按照上面的存儲結構，根結點為 arr[0] ，返回即可。
移除最小元素
移除小頂二叉堆的最小元素 removeMin() ，因為移除小頂二叉堆的最小元素（即堆頂元素）之后，需要對堆進行調整，從而使得堆依舊維持其屬性，一般將調整的過程稱為堆化 。
我們以下圖為例進行說明：

?刪除堆頂元素 10 ，然后將最后一個元素 50 作為小頂堆的堆頂：

然后從堆頂元素 50 開始進行堆化。
第一步：計算當前堆頂元素 50（i = 0） 的左孩子?l = arr[2 * i + 1] = arr[1] = 15 ，以及右孩子?l = arr[2 * i + 2] = arr[2] = 20 ，然后比較三者，選擇出三者的最小值 15 ，將 15和 50 進行交換，繼續對值為 50 的頂點（i = 1）的子樹進行堆化：?

第二步：計算當前要進行堆化的結點 50（i = 1） 的左右孩子，左孩子?l = arr[3] = 45 ，右孩子不存在，比較 50 和 45 ，發現 50 > 45 ，交換兩者，然后繼續對值為 50 的頂點（i = 3）的子樹進行堆化：

第三步：計算要進行堆化的結點 50 (i = 1) 的左右孩子，發現不存在，所以結點 50 已經到葉子結點，整棵樹堆化完成啦（其實這個堆化的過程還是挺簡單的，我們后面刪除等還會用到堆化的）。

更新給定下表的值
這里有一個假設是 new_val < val 的值，如果 new_val > val ，那么就是對更新的結點進行堆化，所以就不單獨進行處理。還想兩種都處理，加個 If...else... 就可以啦。這個操作和堆化的操作相反，我們是從被更新的結點開始向上回溯，直到結點的值大于父結點的值停止

我們將下標為 4 的結點 50 的值更新為 8 ：
第一步：判斷結點 8（i = 4） 的父結點 15（ i=(4 - 1)/2 = 1 ） 的大小關系，8 < 15 ，交換 8 和 15 ，然后結點 8（i = 1） 繼續做判斷：

第二步：判斷結點 8（i = 1） 與其父節點 10（ i=(i - 1)/2 = 0 ）的大小關系，8 < 10 , 交換 8 和10 ：

第三步：判斷結點 8（i = 0），發現其本身已為根結點，沒有父結點，更新結束

插入結點
插入結點 insert() ：將一個新結點插入到樹的末尾，如果新結點的值大于其父結點的值，插入就直接完成了；否則，類似于 updateKey() 操作，向上回溯修正堆。
比如，還是剛才的圖，我們插入結點 30（i = 5） ，由于其值大于父結點的值 20 ，并沒有違反堆的屬性，直接插入完成。

在插入結點 30 的基礎上，我們再插入結點 9（i = 6） ：

新插入結點的值 9（i = 6）小于父結點 20（i = 2） 的值，故交換結點 9 和 20 ，然后繼續判斷值為 9（i = 2） ：

判斷結點 9（i = 2） 與其結點 10（i = 0） 的值， 9 < 10 ，交換 9 和 10 ，然后繼續判斷值 9（i = 2） ：

發現值 9（i = 2） 已經是根結點了，插入完成?

刪除結點

刪除結點 delete() : 刪除一個結點的時間復雜度也是 。將要刪除的結點用無窮小?INT_MIN 替換，即調用?updateKey(i, INT_MIN) ; 然后再將堆頂元素 INT_MIN 移除，即調用?removeMin()?

比如，我們刪除結點 15（i = 1），第一步，調用?update(1, INT_MIN) 將該結點的值替換為INT_MIN :

?第二步：調用?removeMin() 函數將 INT_MIN 移除即可

5.簡單的選擇排序與堆排序代碼演示

?簡單的選擇排序

#include<stdio.h>
#include<stdlib.h>
#define maxx 100
int a[maxx],n,t;
int minn; 
int main()
{int minn;//最小元素的下標 scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}//簡單選擇排序:就地排序， 時間復雜度O(n^2) ,不穩定的排序 //簡單選擇排序:進行n-1趟排序，每次都在亂序區中選擇一個最小的元素，放在亂序的第一個位置，此時有序區+1，亂序區-1 for(int i=1;i<=n-1;i++)//控制循環趟數{minn=i; for(int j=i+1;j<=n;j++)//控制亂序區，去找最小的元素的位置{if(a[j]<a[minn]){minn=j;}}//把minn位置的元素放在亂序區的第一個位置，即i位置if(minn!=i){int t=a[i];a[i]=a[minn];a[minn]=t; }	} 	 for(int i=1;i<=n;i++){printf("%d ",a[i]);}printf("\n");return 0;
}

堆排序

#include<stdio.h>
#include<stdlib.h>
#define maxx 100
/*升序排列 堆排序:就地排序，不穩定 ，時間復雜度O(nlogn) n個元素，保存在a數組中，直接在a數組中
1.初始化成一個小頂堆：下標最大的內部節點的下標是幾？最后一個內部節點的下標是幾？n/2
（1）找到最后一個內部節點（n/2）,依次調整每棵子樹調整過程：依次向下比較調整：若該節點比左右孩子節點中的最小值大，進行交換，直到不滿足該條件位置
2.在小頂堆的基礎上，進行堆排序循環n-1次：（1）輸出（刪除）根節點；（2）最后一個位置的節點代替根節點
（3）向下調整
---輸入最后一個元素
3.堆中插入一個元素：
（1）把元素放到數組最后
（2）向上和父親節點比較進行調整*/
void downAdjust(int a[],int i,int m)//對以 下標i的元素 為根節點的子樹進行向下調整 
{//now是當前調整的節點，next是now的孩子，也是下一次要調整的節點 int now=i;int next;int t;while(now*2<=m){next=now*2;//now的左孩子if(next+1<=m&&a[next+1]<a[next]){next=next+1;//now的右孩子 }if(a[now]<=a[next]){break;} else{t=a[now];a[now]=a[next];a[next]=t;now=next;}} 	 	
}
void upAdjust(int a[],int n)
{//now是當前調整的節點，next是now的父親，也是下一次要調整的節點int now=n;int next; int t;while(now>1){next=now/2;// now的父親if(a[next]<=a[now])//父親節點比當前節點大 {break;}else{t=a[now];a[now]=a[next];a[next]=t;now=next;}} 		
} 
int main()
{int n;//元素個數int a[maxx];// scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}
//把a數組初始化成小頂堆for(int i=n/2;i>=1;i--){downAdjust(a,i,n);} 
//堆排序int m=n;int t;for(int i=1;i<=n;i++){printf("%d ",a[1]);t=a[1];a[1]=a[m];a[m]=t;m--;downAdjust(a,1,m);} printf("\n");for(int i=1;i<=n;i++){printf("%d ",a[i]);}printf("\n");
//在堆中插入一個元素；n++;scanf("%d",&a[n]);upAdjust(a,n);return 0;
}
//堆的應用--優先隊列 

---

總結

一般算法競賽時直接用sort()函數就可以解決排序問題啦，這里的諸多排序方法我們需要掌握思想就好啦！