一. 冒泡排序
1. 思想：利用比較相鄰的兩個元素，發現兩個數前者大于後者則進行交換，這樣每一輪可以把最大數放到後面，隻要做n輪便可以使得序列有序。
2. 舉例，例如序列 8 7 3 4 5 0 1
第一輪：8 7 3 4 5 0 1
8 7 3 4 5 0 1 -> 7 8 3 4 5 0 1
7 8 3 4 5 0 1 -> 7 3 8 4 5 0 1
7 3 8 4 5 0 1 -> 7 3 4 8 5 0 1
7 3 4 8 5 0 1 -> 7 3 4 5 8 0 1
7 3 4 5 8 0 1 -> 7 3 4 5 0 8 1
7 3 4 5 0 8 1 -> 7 3 4 5 0 1 8 // 得到最大值8在最後一個位置
第二輪：7 3 4 5 0 1
...........
3. 從上面的例子我們可以知道，冒泡排序的時間複雜度為O(n^2)，不需要額外的空間輔助，是一個穩定的算法
4. 示例代碼
二. 插入排序
1. 思想：每次選擇未排序序列的第一個數插入已經排好序的序列中，使得這個序列依然有序
2. 舉例：例如序列 8 7 3 4 5 0 1
第一次：未排序序列為8 7 3 4 5 0 1，第一個數是8，沒有排好的序列，是以排好序列為8
第二次：未排序序列為7 3 4 5 0 1，第一個數7，排好序序列為8，則插入到8前面，序列為7 8
第三次：未排序序列為3 4 5 0 1，第一個數為3，排好序序列為3，則插入到7前面，序列為3 7 8
........
3. 隻要把所有的未排序的數全部插入到已經排好序的序列中，這樣整個序列就是有序的。時間複雜度為O(n^2)，是一個穩定的排序算法
三. 選擇排序
1. 思想：每次從未排序的序列中選擇一個最小的數未排序序列第一個數交換，相當于每次選擇一個最小的數放到排好序的序列最後一個位子，當未排序序列為空的時候整個序列即為有序
2. 舉例：例如序列8 7 3 4 5 0 1
第一次：序列 8 7 3 4 5 0 1，未排序序列最小的數0，和8交換，此時排好序序列為0
第二次：序列 0 7 3 4 5 8 1，未排序序列最小的數1，和7交換，此時排好序序列為0 1
第三次：序列 0 1 3 4 5 8 7，未排序序列最小的數3，本身不用交換，此時排好序序列為0 1 3
...............
3. 當未排序序列為空的時候說明整個序列為有序，時間複雜度為O(n^2)，是一個不穩定的排序算法
四. 快速排序
1. 思想：利用一個基準arrNum[k]每次把區間[l,r]劃分成兩個部分[l,k-1],[k+1,r]使得[l,k-1]這個子區間的所有值全部小于等于arrNum[k]，[k+1,r]這個區間的值全部大于等于arrNum[k]的值，然後遞歸對這兩個子區間進行排序。
2. 舉例：例如序列8 7 3 4 5 0 1，每次選擇區間中間那個數作為基準
第一次：區間為[0, 6]，選擇基準為arrNum[3] = 4
（1）先把基準4和最後一個數交換，得到8 7 3 1 5 0 4
（2）設定兩個指針p1和p2，p1用來枚舉所有數，p2用來儲存左子區間全部小于基準的下标，初始化p1和p2都是指向區間左端點
（3）手動推算結果如下
3. 快速排序時間複雜度為O(NlogN)，是一個不穩定的算法，有可能會退化為O(n^2)，不需要額外的空間
五. 歸并排序
1. 思想：利用分治的思想，每次把要排序的區間平均劃分成兩部分，然後遞歸排序，再合并這兩個區間
2. 舉例：例如序列8 7 3 1 5 0 4
3. 歸并排序的時間複雜度為O(NlogN)，是一個穩定的排序算法，但是需用一個和原來一樣大的記憶體空間
六. 堆排序
1. 堆排序利用堆的性質，最小堆滿足根結點的值比左右子樹都小，最大堆滿足根結點的值比左右子樹都大
2. 一個無序系列建立最小堆方法是，從第一個葉子到根結點，每個結點往下調整，調整完所有結點之後即為最小堆
為什麼葉子結點不用調整？因為葉子結點已經滿足最小堆的性質
3. 一個無序序列調整為最小堆的過程，序列為8 7 3 4 5 0 1
4. 建立最小堆的時間複雜度為O(n)，很多人認為是O(NlogN)，為什麼不是呢？證明如下
假設堆中有N個元素，則樹高為H = logN，對于樹高為h的結點建堆時間複雜度為O(H-h)。是以從最底層到根結點所有結點的建堆時間複雜度和為
S = 0*2^(H-1)+1*2^(H-2)+2*2^(H-3)+........+(H-1)*2^0
<= 2^(H)+2^(H-1)+2^(H-2)+.......+2^0
<= 2^(H+1)
因為H = logN，則2^(H+1) = 2^H*2 = 2N，則時間複雜度為O(N)。
5. 建立最小堆代碼
6. 堆排序隻需要每次把最小堆的根結點值取出并删除根結點，然後把最後一個葉子結點補到根結點并删除指，然後從根結點往下調整即可，時間複雜為O(NlogN)，是一個不穩定的排序算法，不需要額外空間
總結：
穩定排序算法：冒泡排序、插入排序、歸并排序、基數排序
不穩定排序算法：選擇排序、快速排序、堆排序、希爾排序