Ch8: Sorting in Linear Time

理論上在不外加任何限制時，大部分排序演算法都是是 \(O(\log n)\)；然而當我們加上一些限制後，排序時間可以縮段到線性時間 \(O(n)\)。本章要來介紹如何達到線性時間排序。

8-1 Lower Bounds for Sorting

• 比較型排序的下限是 \(O(\log n)\)
  • e.g. Insertion sort, Quicksort, Heapsort…
  • 無論如何優化都無法突破
    
    
• 如果要達到線性時間，就不能只靠元素間的比較。

8-2 Counting Sort

• 限制：輸入的 key 必須是非負整數且範圍有限
• 時間複雜度：\(O(n+k)\)
• 流程：
  • 範例：[6,8,8,9,4,4,4,3,2,1]
  1. 製作一個長度為 k = 10 的 array
     
     
  2. 計算每筆資料出現的次數
     
     
  3. 將每一筆資料依出現次數照順序放入 array
     
     
  4. 排序完成後結果如下：
     
     

8.3 Radix sort

• 將不同位元分開依序比較，比到最高位即完成排序
• 時間複雜度：\(O(d(n + k))\)
  • d = 元素的位數
  • k = 每個位數的範圍
• 流程：
  • 由低位排到高位
  • 每一位使用 counting sort
    
    

8-4 Bucket sort

• 限制：輸入要均勻分布在某個範圍
• 時間複雜度：\(O(n)\)
  • 資料分布均勻 -> \(O(n)\)
  • 資料分布**不均勻 **-> \(O(n^2)\)
• 流程：
  • 先把資料放進 bucket 裡面
  • 在 bucket 裡面再用其他排序