《漫畫算法2: 小灰的算法進(jìn)階》第一章 排序算法進(jìn)階
什么是選擇排序
選擇排序：每一輪選出最小元素直接交換到左側(cè)
選擇排序時(shí)間復(fù)雜度：O(n^2)
選擇排序空間復(fù)雜度：O(1)
選擇排序具有不穩(wěn)定性
什么是插入排序
插入排序：維護(hù)一個(gè)有序區(qū)，把元素一個(gè)個(gè)插入有序區(qū)的適當(dāng)位置，直到所有元素都有序?yàn)橹埂?/p>
插入排序的優(yōu)化
3與6進(jìn)行比較，3<6，6復(fù)制到它的下一個(gè)位
3與5進(jìn)行比較，3<5，5復(fù)制到它的下一個(gè)位
插入排序最壞的時(shí)間復(fù)雜度O(n^2)
插入排序的空間復(fù)雜度O(1)
什么是希爾排序
希爾排序：逐步分組進(jìn)行粗調(diào)，再進(jìn)行直接插入排序的思想上面示例中所使用的分組跨度（4，2，1），被稱為希爾排序的增量，增量的選擇可以有很多種。在示例中所用的逐步折半的增量方法，是Donald Shell在發(fā)明希爾排序時(shí)提出的一種樸素方法，被稱為希爾增量。
希爾排序的優(yōu)化
為了保證分組粗調(diào)沒有盲區(qū)，每一輪的增量需要彼此“互質(zhì)”，也就是沒有除1之外的公約數(shù)。
其中最具代表性的是Hibbard增量和Sedgewick增量。
Hibbard的增量序列如下：
1, 3, 7, 15……
通項(xiàng)公式為2k-1
利用此種增量方式的希爾排序，最壞時(shí)間復(fù)雜度是O(n^(3/2))
Sedgewick的增量序列如下：
1, 5, 19, 41, 109……
通項(xiàng)公式為9×4k-9×2k+1或者4k-3×2k+1。
利用此種增量方式的希爾排序，最壞時(shí)間復(fù)雜度是O(n^(4/3))
希爾排序是不穩(wěn)定排序
什么是歸并排序
（p1，p2，p是三個(gè)輔助指針，用于記錄當(dāng)前操作的位置。）
由于1<2，所以把元素1放入大集合，指針p1和p各右移一位
歸并排序的時(shí)間復(fù)雜度為O(nlogn)
歸并排序的空間復(fù)雜度為O(n)
歸并排序是穩(wěn)定排序，兩個(gè)值相同的元素在歸并之后，左側(cè)的元素仍然在左，右側(cè)的元素仍然在右
基數(shù)排序
基數(shù)排序(Radix Sort)：把字符串元素按位拆分，每一位進(jìn)行一次計(jì)數(shù)排序的算法
基數(shù)排序既可以從高位優(yōu)先進(jìn)行排序（Most Significant Digit first，簡(jiǎn)稱MSD），也可以從低位優(yōu)先進(jìn)行排序（Least Significant Digit first，簡(jiǎn)稱LSD）
基數(shù)排序的時(shí)間復(fù)雜度是O(k(n+m))
基數(shù)排序的空間復(fù)雜度為O(n+m)
基數(shù)排序是線性排序算法
小結(jié)
