目錄
排序
選擇排序 O(n2)
不穩定：48429
歸并排序 O(n log n) 穩定
插入排序 O(n2)
堆排序 O(n log n)
希爾排序 O(n log2 n)
圖書館排序 O(n log n)
冒泡排序 O(n2)
優化：
基數排序 O(n · k)
快速排序 O(n log n)【分治】 不穩定
桶排序 O(n + k)
計數排序 O(n + k)
鴿巢排序 O(n + D)
排序
什么是穩定排序算法：數據先后次序不變
選擇排序 O(n2) 歸并排序 O(n log n)插入排序 O(n2) 堆排序 O(n log n)希爾排序 O(n log2 n) 圖書館排序 O(n log n)冒泡排序 O(n2) 基數排序 O(n · k)快速排序 O(n log n) 桶排序 O(n + k)計數排序 O(n + k)鴿巢排序 O(n + D)：
選擇排序 O(n2)
? 先找出最小值，將其與第一個位置的元素進行交換
? 對剩余的數據重復以上過程，直至排序結束
不穩定：48429
歸并排序 O(n log n) 穩定
歸并：如果有兩個分別有序的數組，可以用雙指針合并成一個完全有序的數組
可以遞歸寫
也可以從0開始
歸并1-1? 1-1? 1-1? 1-1
歸并? ?2-2? ? ? ? ? 2-2
歸并? ? ? ? ?4-4
完成！
插入排序 O(n2)
假設前面 k 個元素已經按順序排好了，在排第 k+1個元素時，將其插入到前面已排好的 k 個元素中，使得插入后得到的 k+1 個元素組成的序列仍按值有序。
堆排序 O(n log n)
希爾排序 O(n log2 n)
基本過程描述如下：
① 把序列按照某個增量（gap）分成幾個子序列，對這幾個子序列進行插入排序。
② 不斷縮小增量，擴大每個子序列的元素數量，并對每個子序列進行插入排序。
③ 當增量為 1 時，子序列就是整個序列，而此時序列已經基本有序了，因此只需做少量的比較和移動就可以完成對整個序列的排序
出發點：插入排序在元素基本有序的情況下，效率很高。
gap：初始值設為 n/2，然后不斷減半。
圖書館排序 O(n log n)
冒泡排序 O(n2)
? 走訪需要排序的序列，比較相鄰的兩個元素，如果他們的順序錯誤就把他們交換過來。
? 不斷重復上述過程，直到沒有元素需要交換
具體過程：
? 將第 1 個和第 2 個元素進行比較，如果前者大于后者，則交換兩者 的位置，否則位置不變；然后將第 2 個元素與第 3 個元素進行比較， 如果前者大于后者，則交換兩者的位置，否則位置不變；依此類推， 直到最后兩個元素比較完畢為止。這就是第一輪冒泡過程，這個過程 結束后，最大的元素就“浮”到了最后一個位置上。
? 對前面 n-1 個元素進行第二輪冒泡排序，結束后，這 n-1 個元素中 的最大值就被安放在了第 n-1個位置上。
……執行n-1輪
優化：
簡單優化：
如果在某輪冒泡過程中沒有發生元素交換，這說明整個序列已經排好序了，這時就不用再進行后面的冒泡過程，可以直接結束程序
進一步優化：
假設有 100 個數組成的數組，僅前面10個無序，后面90個都已排好序且都大于前面10個數字，那么在第一輪冒泡過程后，最后發生交換的位置必定小于10，且這個位置之后的數據必定已經有序了，記錄下這位置，第二輪遍歷是只要到這個位置就可以了。記錄每輪遍歷最后發生交換的位置，下次遍歷只需到此位置為止
基數排序 O(n · k)
先排個位，再排十位，再排百味（30次）
快速排序 O(n log n)【分治】 不穩定
快速排序采用的是分而治之思想：將原問題分解為若干個規模更小但結構與原問題相似的子問題，然后遞歸求解這些子問題，最后將這些子問題的解組合為原問題的解
1.以第一個元素為基準書，使得基準書左邊只有比他小的，右邊只有比他大的
2.然后對基準書兩邊的數組分別進行操作1
分治：分成相同的子問題，用遞歸求解；子問題相互獨立
dp：子問題不一定相同，具有最優子結構；子問題相互依賴
