最壞情況下時間複雜度：O(n^2) ，一般是O(n^1.3)，是一個不穩定算法。只適用於順序存儲。空間複雜度：O(1)
插入排序總結
算法名稱時間複雜度空間複雜度是否穩定適用於直接插入排序O(n^2)O(1)穩定順序存儲和鏈式存儲折半插入排序O(n^2)O(1)穩定順序存儲希爾排序O(n^2)O(1)不穩定順序存儲
3.交換排序
3.1.冒泡排序
基本思想：假設待排序表長為n，從後往前（從前往後），兩兩比較相鄰元素的值，若為逆序（即A[i-1]>A[i]），則交換他們直到序列比較結束。
第一次循環從前往後進行比較，我們發現最總我們將最大的值9放到了最後面的位置，因為我們的比較的時候如果前面的值大於後面的值就會交換位置，所以出現了這種情況。
所以再冒泡排序中有這樣的特點：一次冒泡會將一個元素放置到它最終的位置上 。也就是一次冒泡可以確定一個元素的位置，就如上圖，接下來我們只需要對9元素前面的位置進行冒泡就又可以確定一個元素的位置，然後依次(n-1次)冒泡即可將一個亂序序列，排成一個遞增的序列。
代碼實現：
<code>void BubbleSort(ElemType A[],int n){
for(int i=0;i-1;i++){
bool flag=false;
for(int j=n-1;j>i;j--){
if(A[j-1].key>A[j].key){
swap(A[j-1],A[j]);
flag=true;
}
}
if(flag==false){
return;
}
}
}
/<code>時間複雜度（最好、平均、最壞）：O(n)、O(n2)、O(n2)，空間複雜度：O(1)，是穩定的算法。適用於順序存儲和鏈式存儲。
3.2.快速排序
基本思想：在待排序表L[1....n] 中任取一個元素pivot 作為基準，通過一趟排序將待排序表劃分為具有如下特點的兩部分：（這裡我們默認選取第一個元素作為基準）
這裡第一次排序（一趟Partition）之後pivot左側的元素全是小於pivot的，右側的元素全是大於pivot的
我們可以發現一次排序後會將一個元素pivot放置到它的最終位置上 ，因為pivot左側的元素全是小於pivot的，右側的元素全是大於pivot的。
接下來對pivot前面的這部分在進行一次快速排序，後面的部分再進行一次快速排序。同樣可以得到兩個元素放置到它們最終的位置上。讓後繼續…【快速排序的思路】
Partition的基本思路：
初始化標記low為劃分部分的第一個元素的位置，high為最後一個元素的位置，然後不斷地移動兩標記交換位置：
- high向前移動找到第一個比pivot小的元素
- low向後移動找到第一個比pivot大的元素
- 交換當前兩個位置的元素
- 繼續移動標記，執行 1、2、3 的過程，直到low大於等於high為止
Partition代碼實現：
<code>
int Partition(ElemType A[],int low,int high){
ElemType pivot=A[low];
while(low/<code>第一次進行Partition：
接下來需要利用返回的這個基準的下標將數組劃分為兩部分，分別進行Partition
快速排序代碼實現
<code>
void QuickSort(ElemType A[],int low,int high){
if(lowint pivotpos=Partition(A,low,high);
QuickSort(A,low,pivotpos-1);
QuickSort(A,pivotpos+1,high);
}
}
/<code>可以發現 快速排序是一個不穩定 的算法。時間複雜度：O(high-low+1)
快速排序的執行過程：
我們可以發現整個過程類似一顆樹，也就是說如果我們基準選擇的好，那麼這個樹的深度就比較淺，相對的遞歸次數就比較少，那對應工作棧的長度就越小，空間利用就越小。所以它的最好、平均空間複雜度
如果一個序列初始基本有序或逆序的情況如上，則最壞空間複雜度為O(n)。最壞的時間複雜度O(n^2)
交換排序總結
算法時間複雜度空間複雜度是否穩定適用於冒泡排序O(n^2)O(1)穩定順序存儲和鏈式存儲快速排序O(nlog2n)O(log2n)不穩定順序存儲（鏈式存儲）
4.選擇排序
4.1.簡單選擇排序
基本思想：每一趟在後面n-i+1(i=1,2…n-1)個待排序元素中選取關鍵字最小的元素，作為有序子序列的第i個元素，直到n-1趟做完，待排序元素只剩下1個。
綜上：一趟排序會將一個元素放置在最終的位置上
代碼實現
選擇排序是不穩定的，另外根據算法我們可以看無論初始序列是什麼樣的我們都要進行逐個遍歷，所以時間複雜度是O(n^2)，與初始序列無關。空間複雜度為O(1)，適用於順序存儲和鏈式存儲。
4.2.堆排序
什麼是堆?
堆是一棵完全二叉樹，而且滿足任何一個非葉結點的值都**不大於(或不小於)**其左右孩子結點的值。
如果是每個結點的值都不小於它的左右孩子結點的值,則稱為大頂堆。
如果是每個結點的值都不大於它的左右孩子結點的值,則稱為
小頂堆。
什麼是堆排序?
我們知道對於一個堆來說,它的根結點是整個堆中所有結點的值的最大值(頂堆或者最小值(小頂堆)所以堆排序的思想就是每次將無序序列調節成一個堆,然後從堆中選擇堆頂元素的值,這個值加入有序序列,無序序列減少一個,再反覆調節無序序列,直到所有關鍵字都加入到有序序列。
所以堆排序最重要的操作就是將無序序列調節成一個堆。
12 52 19 45 23 45 92 （以大頂堆排序為例），首先排成一個完全二叉樹序列
①建堆對初始序列的完全二叉樹調整成一個大頂堆調整方法：二叉樹由下至上由右至左 (數組的下標由大到小)。檢查每個結點是否滿足大頂堆的要求,如果不滿足進行調整。
- 45 23 45 92 四個結點都是葉子結點,不需要調整
- 19<45<92，所以要用92和19進行交換
- 52>45且>23 不需要調整
- 12<52<92 要用92交換12
- 12<19<45 要用45和12交換
- 到這裡就建好了一個大頂堆
②將堆頂結點和最後一個結點19交換，也就是將最大值92移動到數組的最末尾，有序序列中加入了結點92，無序序列減少結點92，到這裡堆排序的第一趟完成。【此時二叉樹不滿足堆的性質了，需要調堆】
③調堆：調整二叉樹的結點使得滿足大頂堆的要求。調整方法和建堆時一樣。
- 45>12不需要調整，52也不需要
- 19<45<52需要將結點19和52交換
- 19<23<45需要將結點19和45交換
- 到這裡又調成了一個大頂堆類似之前的操作，選出根結點52作為有序序列的第二個數值
二叉樹性質5：
對完全二叉樹按從上到下、從左到右的順序依次編號1,2…,N,則有以下關係
①當i>1時，結點i的雙親結點編號為i/2，即當i為偶數時，其雙親結點的編號為i/2。它是雙親結點的左孩子，當i為奇數時，其雙親結點的編號為(i-1)/2，它是雙親結點的右孩子。
②當2i≤N時，結點i的左孩子編號為2i，否則無左孩子。
③當2i+1≤N時，結點i的右孩子編號為2i+1，否則無右孩子。
設最後一個結點編號為N，N等於二叉樹中結點數量，它肯定是葉子結點。所以 第一個可能需要調整的非葉結點的下標為N/2 ，從它的左孩子開始檢查，它的左孩子下標為*N/2 2，如果發生交換,下一輪檢查交換過的結點的左右孩子
代碼實現
空間複雜度：堆排序只需在交換節點的時候需要額外存儲空間來輔佐，所以空間複雜度為O(1)
時間複雜度：堆排序的總時間可以分為①建堆部分+②n-1次向下調整堆=O(n)+
=
穩定性：不穩定
5.歸併排序
假定待排序表含有n個記錄，則可以看成是n個有序的子表，每個子表長度為1，然後兩兩歸併，得到n/2 個長度為2或1的有序表；再兩兩歸併，……如此重複，直到合併成一個長度為n的有序表為止，這種排序方法稱為
2-路歸併排序。例如：49 38 65 97 76 13 27
①首先將整個序列的每個關鍵字看成一個單獨的有序的子序列
②兩兩歸併,49和38歸併成{38 49},65和97歸併成(65 97,}76和13歸併成(13 76}，27沒有歸併對象
③兩兩歸併,{38 49}和{65 97歸併成{38 49 65 97}，{13 76}和27歸併成{13 27 76}
④兩兩歸併,{38 49 65 97}和{13 27 76}歸併成{13 27 38 49 65 76 97}
更據這個排序方法可以看出相當於使用了分治和遞歸的方法
代碼實現
<code>ElemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType));
void Merge(ElemType A[],int low,int mid,int high){
for(int k=low;k/<code>時間複雜度：一共n個元素
Merge第①趟:子序列長度為2.所以有n/2對子序列,每個子序列需要執行1次 Merge 。Merge時間複雜度為子序列長度之和，即2。所以第①趟 merge的時間複雜度為(n/2*2)=0(n)
第②趟 Merge:子序列長度為4,所以有n/4對子序列,每個子序列需要執行1次 Merge, Merge時間複雜度為子序列長度之和即4所以第②趟 merge的時間複雜度為O(n/4*4)=(n)
第k趟歸併：子序列長度為2k，所有有n/2k對子序列。
當n/2^k=1時,k=log2n，此時需要歸併的兩個子序列長度為n/2，只需要一次 Merge就能實現整個序列有序。所以一共執行了k=log2n趟排序,每趟排序的時間複雜度都是(n)，所以整個歸併排序的時間複雜度為O(nlog2n)
空間複雜度：因為需要將這個待排序序列轉存到一個數組,所以需要額外開闢大小為n的存儲空間,即空間複雜度為O(n)
**穩定性：**穩定的
6.基數排序
基數排序(也叫桶排序)是一種很特別的排序方法,它不是基於比較進行排序的,而是採用多關鍵字排序思想(即基於關鍵字各位的大小進行排序的),藉助“分配”和“收集”兩種操作對單邏輯關鍵字進行排序。基數排序又分為**最高位優先(MSD)排序和最低位優先(LSD)**排序。
例子：53，3，542，748，14，214，154，63，616
首先補充位數：053，003，542，748，014，214，154，063，616
桶實際是一個隊列，先進先出（從桶的上面進，下面出）
第一次"分配"（隊列從上入隊）（我們這裡採用最低位優先 ：即關鍵字補充後的個位進行比較，然後各位數對應同的序號，如果個位數為3，則進入桶3。按照依次進隊）
第一次"收集"（隊列從下出隊）（從桶0到桶9依次出隊，此時可以看出每個關鍵字的個位數依次遞增）
第二次"分配"（隊列從上入隊）（第二次分配很顯然使用關鍵字的十位數字進入桶，同樣是依次入桶）
第二次"收集"（隊列從下出隊）（從桶0到桶9依次出隊，此時可以看出每個關鍵字的十位數依次遞增）
003 014 214 616 542 748 154 053 063
第三次"分配"（隊列從上入隊）
第三次"收集"（隊列從下出隊）（從桶0到桶9依次出隊，此時可以看出每個關鍵字的百位數依次遞增）
003 014 053 063 154 214 542 616 748
此時發現由於關鍵字現在三個位數都排列有序，所以整個關鍵字序列都排列有序。
關鍵字數量為n，關鍵字的位數為d，比如748 d=3，r為關鍵字的基的個數,就是組成關鍵字的數據的種類,比如十進制數字一共有0至9共10個數字,即r=10
空間複雜度：需要開闢關鍵字基的個數個隊列,所以空間複雜度為O®
時間複雜度：需要進行關鍵字位數d次"分配"和"收集"，一次分配需要將n個關鍵字放進各個隊列中，一次收集需要將r個桶都收集一遍，所以一次分配和一次收集時間複雜度為O(n+r)。d次就需要O(d(n+r))的時間複雜度。
穩定性：由於是隊列,先進先出的性質,所以在分配的時候是按照先後順序分配,也就是穩定的,所以收集的時候也是保持穩定的。即基數排序是穩定的排序算法。
最高位優先則是從最高位開：例子：53，3，542，748，14，214，154，63，616
其實我們這裡可以對桶中關鍵字個數不為1的桶遞歸排序
首先我們現在針對桶0進行排序：即同樣拿出10個桶對桶中關鍵字的次高位進行分配
同樣看有沒有關鍵字個數不為1的桶。此時各個桶中都只有一個關鍵字,遞歸結束,收集各桶返回到上一層。此時桶中是這個樣子。
收集各桶：得到有序序列003 014 053 063 154 214 542 616 748
7.理木客
數據結構相關知識，公眾號理木客同步更新中，歡迎關注！
