# 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 裡面再用其他排序