线性算法

基数排序是一种非比较的排序算法。它基于对每个子关键字在值域上的计数实现整体的排序。对于整数，可以在$\mathrm{O}(kn + \sum\limits_{i=1}^{k}w_i)$的线性时间内完成排序，其中$w_i$为每个关键字的值域大小。

以下代码将对int范围内的整数，以前$16$位和后$16$位为关键字进行排序。可以发现，在数据个数$n \leq 7\times 10^4$，其表现不如基于比较的快速排序算法。因此，在值域很大而数据较少时，应合理调整策略。

（更多…）