快排虽称快速排序，但是其严格来讲
只能称为是基于比较的排序算法中相对很优秀的算法
排序算法的时间效率下界是O(nlogn)
是仅针对基于比较的排序算法的
而今天讲的O(n)的基数排序算法
是一种基于内容而不基于比较的排序算法
下面进入正题，先来尝试了解基数排序算法
给出几个数
239，156，734，237，112，320，255，193
我们尝试这样排序，第一步把几个数分为
[156,112,193] [239,237,255] [320] [734]
即仅按最高位分成几堆，然后每堆中是保留原顺序的
第二步仅按次高位在每堆中继续调整
[112,156,193] [239,237,255] [320] [734]
最后仅按最低位在每堆中继续调整
[112,156,193] [237,239,255] [320] [734]
这时排序就完成了
上面这种排序算法我们称为最高位优先(Most Significant Digit first)法，简称MSD法
同理还有最低位优先(Least Significant Digit first)法，简称LSD法，此方法可参考百度百科
LSD非常丑的参考代码
#include <vector> #include <iostream> #include <algorithm> #define pb push_back #define rep(i, j, k) for(int i = j;i <= k;i ++) using namespace std; int n, a[2000010]; int maxa, maxl, k = 1; vector <int> e[2][10]; int main() { cin >> n; rep(i, 1, n) { cin >> a[i]; maxa = max(maxa, a[i]); e[1][a[i] % 10].pb(a[i]); } while(maxa) { maxl ++; maxa /= 10; } rep(i, 2, maxl) { k *= 10; rep(j, 0, 9) for(int t = 0; t < e[!(i & 1)][j].size();t ++) e[i & 1][e[!(i & 1)][j][t] / k % 10].pb(e[!(i & 1)][j][t]); rep(j, 0, 9) e[!(i & 1)][j].clear(); } rep(i, 0, 9) for(int j = 0;j < e[maxl & 1][i].size();j ++) cout << e[maxl & 1][i][j] << " "; return 0; }
当然写这段另外认识到了一个问题
string和vector中的size()返回值类型均为unsigned int
若size() = 0的话，那么size() - 1 = 2^32 - 1
另外也因此，输出中间变量来查错的时候强烈建议使用cout
我当时查错用printf("%d ", size() - 1)，输出当然是-1
然而cout << size() - 1，答案就很明了了
基数排序正确性证明略
时间复杂度分析简单来说即O(maxLen * n)
maxLen为最长数字位数，n为排序元素数字个数
空间复杂度直接O(n + 2n)就可以满足
直接开O(maxL * n) 是非常浪费空间的
还有可能内存爆炸
有的没的碎碎念:
基于比较的排序算法效率下界是O(nlogn)
而基于内容的三种排序算法:桶排序，基数排序，计数排序理论效率均为O(n)级别
而且个人看起来，桶排序和计数排序是没有什么营养的
桶排是用某种映射方式将n个元素尽量均匀地分装在一些有序桶中
然后每个桶分别排序(这里可以递归桶排，可以直接快排)
并且当桶的个数恰好n个时，就变成了计数排序......
然而我们需要注意基于内容的排序算法的三个特点：
1.对排序的元素有一些要求，比如元素范围，元素长度等
2.基本都需要采取空间换时间的策略，这种策略有时并不好
3.因为要基于内容，所以对排序元素类型有要求
综上这些算法的使用范围是非常有限的
所以注定了他们是不能像快排一样众人皆知的
末尾补充一个小知识点吧
排序算法的稳定性是指，原排列中相同的两个元素
在排序完成后其相对位置是否与原来保持一致
几个稳定的排序算法:直接插入排序，冒泡排序，归并排序，基数排序
当然有些排序算法的稳定性似乎取决于你对于 < 和 <= 这两个符号的选择...
不再继续讨论
参考资料:基数排序_百度百科