算法基礎-排序方法

比較排序

顧名思義，比較排序就是通過比較數組裡的每個數來排序的算法的統稱，經典的比較排序有：冒泡排序，插入排序，快速排序等。它們都是通過逐一比較各個元素，進而得知每個元素應該待的位置。

為了尋找最佳比較排序算法，我們需要得知比較排序的漸進時間複雜度。但是實際上排序算法通常會受到數組的實際值的影響，是以這裡我們先考慮最壞情況。

在一個長度為 n 的數組 A 裡，欲得知 A[0] 應該待的位置，就需要知道 A[0] 是第幾小的數，如果它是第3小的數字，那麼他就應該出現在第3個位置。

隻需要知道比較的次數，就能求出算法的時間複雜度。

設總共需要比較 x 次，每次比較可以得到兩種不同的可能的排列。

例如數組 [a,b,c]，比較 b 和 c ，則可能對應以下兩種排列

是以，根據比較的次數就可以得到所有排列的個數，一次比較會産生 2 個不同的排列，那麼 x 次比較就會産生 2^x 個不同的排列。但是我們知道數組的長度為 n ，是以最多隻有 n! 種不同的排列

是以可以列出不等式

也就是說，任何基于比較的排序算法，它的時間複雜度至少應該是 O(logn!)

階乘符号讓這個複雜度看起來非常難受，是以我們把階乘展開

是以比較排序的時間複雜度至少應該是 O(nlogn)

在最壞情況下，堆排序和歸并排序的時間複雜度都是O(nlogn)，是以這兩種排序方法比起其它比較排序更優

線性時間排序是指時間複雜度為 O(n) 的排序方法，無論是什麼情況，線性時間排序總會比比較排序更快速，但是它們隻适用于數值分布較小的情況

計數排序先計算每個數字出現的次數，然後再按照大小關系逐一輸出。

例如數組 [6,6,3,4,7,7,3]，首先計算出每個數字出現的次數

是以最終結果是 [3,3,4,6,6,7,7]

這種排序方法隻需要周遊一次數組就可以得到所有數字出現的次數，最終直接根據次數來輸出，但是弊端也非常明顯，如果數字範圍過大，或者出現小數，那麼所列出的表格也會非常大，甚至根本就無法列出表格

基數排序可以看成改進版的計數排序。對于範圍在0~999以内的整數，先将它們按照個位數排序，然後按照十位數(如果沒有就是0)排序，最後再按照百位數排序

每次排序時若遇到相同的數字，則會保持位置不變，等待下一輪排序，是以基數排序是穩定的，但也與計數排序類似，對數值分布的要求很高，對于小數或者字元串，要重新設計分割方法