思維
當處理小序列時，傾向於使用可以達到 O(n) 時間複雜度的算法有以下幾個原因：
- 適應性：像插入排序這樣的算法能夠利用輸入數據的初始有序程度。如果數據已經部分排序（這在小數據集中更有可能），這類算法可以更接近線性性能。
- 內存訪問：小數據集可以完全容納在 CPU 快取中，這樣就減少了訪問主內存的需求。這可以顯著提高 O(n) 算法的速度，因為它們通常具有良好的空間局部性，可以充分利用快取
- 額外開銷：更複雜的算法（如快速排序或歸併排序）通常有更大的設定開銷（例如遞歸棧調用或額外的內存分配）。在小數據集上，這種開銷可能不會得到足夠的平攤，從而使得簡單算法在性能上更有優勢。
排序法比較表格
| 排序演算法 | 平均時間複雜度 | 最好情況 | 最壞情況 | 空間複雜度 | 排序方式 | 穩定性 |
|---|---|---|---|---|---|---|
| 泡沫排序法 | O(n^2) | O(n) | O(n^2) | O(1) | 原地排序 | 穩定 |
| 插入排序法 | O(n^2) | O(n) | O(n^2) | O(1) | 原地排序 | 穩定 |
| 計數排序法 | O(n + k) | O(n + k) | O(n + k) | O(k) | 非原地排序 | 穩定 |
| 桶排序法 | O(n + k) | O(n) | O(n^2) | O(n + k) | 非原地排序 | 穩定 |
Round 1:
選手：泡沫排序法，插入排序法，計數排序法，桶排序法
非原地排序需要額外的內存分配很耗時，因此去除計數排序法，桶排序法
Round 2:
選手：泡沫排序法，插入排序法，計數排序法，桶排序法
泡沫排序法在交換相鄰元素時，涉及到三次賦值操作（使用一個臨時變數進行交換）
插入排序法在找到插入點之前只需要將元素向後移動，這通常只涉及一次賦值操作