該文章為Princeton-Algorithms Part I讀書筆記谐檀，相關視頻在此斩狱。
1. Sort Any Type of Data
-
Comparable接口
只要對象實現(xiàn)了Comparable接口柬姚，它就能夠進行比較。
Comparable接口 -
v.compareTo(w) 方法
- v < w : -1
- v = w : 0
-
v > w : 1
v.compareTo(w)
2. Selection Sort
基本思想：
保持前部分sorted，后部分unsorted。在第i次迭代中佩研，在未排序的部分中找最小的，再將最小的swap到位置i霞揉。
兩個不變性invariants：
- 左半部分由小至大已排序
- 右半部分的數(shù)據(jù)都不小于左半部分
實現(xiàn)
效率
- O(N^2)
- input insensitive：即使是sorted的input也會花O(N^2)的時間
- 對數(shù)據(jù)的移動是最少的旬薯，最優(yōu)的數(shù)據(jù)交換次數(shù)，至多O(N)
3. Insertion Sort
基本思想
保持前部分有序适秩，后部分無序绊序。在第i次迭代中，將第i個數(shù)據(jù)插入到之前排好序的數(shù)據(jù)中的相應位置秽荞。
兩個不變性invariants
- 已排好序的左半部分
- 右半部分目前還從未得到訪問
實現(xiàn)
效率
- best：O(N)骤公，worst：O(N2)，average：O(N2)
- Input sensitive扬跋，對于partially sorted的數(shù)組阶捆，時間可以達到線性O(N)
引入一個概念：逆序對inversion
是指一對各自相對大小錯位的數(shù)據(jù)對。對數(shù)據(jù)的swap操作就是在減少逆序對钦听。
- An array is partially sorted if the number of inversions is ≤ c N.
- 實際上是插入排序的用時是O(I + N)洒试。I是inversion的數(shù)量(最好是0，最差N^2)朴上，N是遍歷數(shù)組的用時垒棋。當逆序對的數(shù)量是n的數(shù)量級，那么稱數(shù)據(jù)partially ordered痪宰。對于這樣的數(shù)據(jù)集叼架，插入排序的效率可以達到線性。（因為交換的次數(shù)是o(n)衣撬，比較的次數(shù)也是O(n)）乖订。
4. Shell Sort
基本思想
相當于一個進階版插入排序。在插入排序中淮韭，當數(shù)據(jù)在找自己的相應位置時垢粮，數(shù)據(jù)的移動一次只移動一位，但在希爾排序中靠粪，數(shù)據(jù)的一次移動h次蜡吧，稱之為h-sort。
基本方法
利用一個increament sequence(1~h)占键。首先開始h-sort昔善，不斷地進行到1-sort(即Insertion sort)。好處在于：
- 對于大的h畔乙，insertion sort的比較步長大君仆，會省去很多比較，因此效率高。
- 對于小的h返咱，由于在之前的sorting中減少了一部分inversions钥庇，所以數(shù)組現(xiàn)在屬于partially sorted，因此insertion sort的效率又得以提升咖摹！
如何決定要用到的Increment Sequence评姨？
Increment Sequence對該算法的效率有影響。該采用怎樣的sequence來做h-sort萤晴，仍然處在一個不斷研究的過程吐句。
實現(xiàn)
效率
理論上確切的數(shù)值還沒有定論！但是用3x+1這樣的序列的話店读，復雜度大概是O(N^1.5)嗦枢，實踐上其實接近了O(NlgN)。
5. 排序問題引出的相關問題：Shuffle
思路1：
給每個數(shù)據(jù)隨機生成一個自然數(shù)屯断，然后再以這個自然數(shù)為key來sort數(shù)據(jù)文虏，結果產(chǎn)生一個uniformly random permutation。
效率：
sort上花銷大殖演。
思路2：Knuth Shuffle -> 線性
進行N次循環(huán)择葡，第i次循環(huán)中，在0 ~ i之間等概率地(uniformly random)生成一個隨機數(shù)r剃氧，最后將a[r]與a[i]的位置交換。
實現(xiàn)
效率
這樣的shuffle方式保證了每種premutation等概率出現(xiàn)(uniformly random)阻星，可以達到線性效率朋鞍。
注意：只能是動態(tài)的部分的范圍中隨機生成一個數(shù)r，不能一直以全局的長度生成一個隨機數(shù)妥箕，這樣的出的結果并不是uniformly random permutation滥酥。
應用
- 德?lián)湎磁?br>
實際應用中實際上由于seed的限制，會有很多bug：
洗牌實現(xiàn)
所以畦幢，實際應用中可以利用硬件來洗牌坎吻，當然，依然不能夠完美宇葱，總之瘦真，完美的隨機洗牌是hard的！
