排序与查找
计数排序
计数排序干脆把比较彻底丢掉。它不问“这个比那个大吗？”，而是问“每个值各有多少个？”。如果键是已知范围 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) 的下界只对比较排序（靠两两比较键来排序的那些）成立。计数排序、基数排序、桶排序都是非比较排序：它们读取键本身的数值，所以当键受限时（例如小整数）能更快。
又称
另见