排序與搜尋
計數排序
計數排序乾脆把比較徹底丟掉。它不問「這個比那個大嗎？」，而是問「每個值各有多少個？」。如果鍵是已知範圍 0..k 內的小整數，你就建一個有 k+1 個計數器的陣列，掃一遍輸入統計每個值出現了幾次，再按順序走訪這些計數器，把每個值按它被數到的次數輸出出去。輸出就這樣排好了序，而沒有任何一個元素被拿去和另一個比較過。
想像給一疊分數從 0 到 100 的考卷排序：做 101 個格子，把每張卷子丟進它分數對應的格子，再從左到右把格子讀出來。要讓它穩定（保持相等鍵的原有先後順序——當每個鍵還附帶額外資料時這很重要），你把計數變成前綴和，給每個值劃出它在輸出裡的那段位置區間，然後從後往前掃描輸入來放置元素。
代價是時間 O(n + k)、空間 O(n + k)，其中 n 是元素個數，k 是值域大小。當 k 與 n 相當時（小而密集的整數鍵），這實際上就是線性的——突破了適用於一切比較排序的 O(n log n) 下界。這並不矛盾：那條下界只管那些靠兩兩比較來獲知順序的演算法；計數排序透過直接利用鍵的數值繞開了它。要當心的是值域：若 k 巨大（例如給 64 位元整數排序），那個 k 大小的計數器陣列會讓它變得不切實際。它也只適用於能給陣列當索引的鍵——整數或能映射成整數的東西，而非任意物件。
std::vector<int> countingSort(const std::vector<int>& a, int k) {
std::vector<int> count(k + 1, 0), out;
for (int x : a) ++count[x]; // tally each value
for (int v = 0; v <= k; ++v)
while (count[v]-- > 0) out.push_back(v); // emit in order
return out;
}排序前：[2, 5, 2, 0, 3, 0] 排序後：[0, 0, 2, 2, 3, 5]——O(n + k)，無比較。
O(n log n) 的下界只對比較排序（靠兩兩比較鍵來排序的那些）成立。計數排序、基數排序、桶排序都是非比較排序：它們讀取鍵本身的數值，所以當鍵受限時（例如小整數）能更快。
又稱
另見