算法导论的第八章是：线性时间排序
我们共分析过四个排序算法：插入排序，归并排序，堆排序以及快递排序，它们有一个共同点，就是都是基于比较的，都属于比较排序算法
通过决策树模型，可以知道比较排序算法的最坏情况下的下界是：nlog(n)
上面的话有点拗口，下面进行简单的分析
决策树，是一棵满二叉树，排序的过程就像从根走到叶的过程, 因为不是小于等于就是大于嘛，所以不是向左走，就是向右走，直到走到叶节点，排序完成。 那么比较的次数，在最坏的情况下，不会多于树的高度。
n的元素的排序，共有 n! 种 情况， 它们都会出现在决策树的叶子节点上
高度为 h 的二叉对， 叶子数目不会多于 2^h 个
因此 n! <= 2^h ----> h > lg(n!) 后者 相当于 nlg(n)
也就是说不管怎么样的决策树，它的高度不会小于 nlg(n)
而一个排序算法，就对应于一棵决策树, 因此在最坏的情况下，它的比较次数 h , 而不管算法设计多么棒 h >= lg(n!)
所以堆排序和合并排序都是渐近最优的。
快速排序在平均情况下，也是渐近最优的。
//-----
排序也可以不基于比较，因此就没有上述限制
计数排序
读了这一节，让我想到了《编程珠玑》（不是《编程珠玑2》) 中的一个问题， 大概是这样：
系统要对一个文件中的记录进行排序，排序后，输出到另一个文件 。 文件的每个记录都是一个小于7位的数字（背景是美国的电话号码）, 记录不重复，记录数目非常多，大概也是近千万。
上面这个过程是一个大系统的一小部分，要求在最好十几秒内就要完成这个过程， 并且大概只有1M的内存空间可以使用。
首先， 1千万个数字是放不进1M的， 1M只能放一百万个数字， 所以不能使用普通的内存排序。 可以采用文件归并排序。 但速度肯定达不到要求。
但是1千万个(bit)， 差不多是1M多一点， 如果用一个位表示一个数字， 那就有望在1M多一点的内在中保存1千万个数字。
该问题最后的解决方案大概是这样的（原文是伪代码，这里使用java实现，并且可以运行，因为可以运行的代码让程序员更兴奋）
等等，我们先产生这样的文件，否则又对什么进行操作呢？
public void prepareData() throws IOException {
long begin = Calendar.getInstance().getTimeInMillis();
int n = 10000000; // 7个0;
int[] data = new int[n]; // 这大概要用 40M内存, 在我们的机子上米关系
for (int i = 0; i < n; i++) {
data[i] = i;
}
shuffle(data); // 打乱它
Writer writer = new BufferedWriter(new FileWriter("data.txt"));
try {
// 选其中的800万个输出
for (int i = 0; i < 8000000; i++) {
writer.write("" + data[i] + "\n");
}
} finally {
writer.close();
}
long end = Calendar.getInstance().getTimeInMillis();
System.out.printf("used: %f(s)", (end - begin) / 1000.0);
}
我们首先按顺序产生一千万个数字，然后打乱它，最后输出到文件data.txt
其中，shuffle 在算法笔记2中有实现过，用的是ruby, 现在我们用java
private void shuffle(int[] data) {
Random rand = new Random();
int n = data.length;
for (int i = 0; i < n; i++) {
int j = rand.nextInt(n);
//swap
int t = data[i];
data[i] = data[j];
data[j] = t;
}
}
在我的机子上大概用了9.3s时间， 产生了一个60.1M的文件。
下面就是排序并且输出到一个文件啦：）
public void hehe() throws IOException {
long begin = Calendar.getInstance().getTimeInMillis();
BitSet bits = new BitSet();
BufferedReader reader = new BufferedReader(new FileReader("data.txt"));
try {
String s = null;
while ((s = reader.readLine()) != null) {
int k = Integer.parseInt(s);
bits.set(k);
}
} finally {
reader.close();
}
Writer writer = new BufferedWriter(new FileWriter("out.txt"));
try {
for (int i = 0, n = bits.length(); i < n; i++) {
if (bits.get(i)) {
writer.write("" + i + "\n");
}
}
} finally {
writer.close();
}
long end = Calendar.getInstance().getTimeInMillis();
System.out.printf("used: %f(s)", (end - begin) / 1000.0);
}
这在我的机子上用了11.2s, 可以说是读写有多快，它就有多快。
在上面的例子，我看到了计数排序的影子， 只不过这个 count = 1，所以简单地用位来实现
计数排序是这样的：
int[] countSort(int[] a, int k) {
int[] c = new int[k]; // 准备好，对所有k个数字进行计数
for (int i = 0; i < c.length; i++) {
c[i] = 0;
}
for (int i = 0, n = a.length; i < n; i++) { // 对数组中的数进行计数
c[a[i]]++;
}
// 到这里为止 c[i] 就是 i 这个数字出现的个数
for (int i = 1; i < c.length; i++) {
c[i] = c[i] + c[i - 1];
}
// 到这里为止 c[i] 就是 < i 数的个数
int[] b = new int[a.length];
for (int i = a.length - 1; i >= 0; i--) {
b[c[a[i]] - 1] = a[i]; // 比a[i] 小的数有 c[a[i]] 个, 我们把它放到相应位置
c[a[i]]--; // 计数减一， 这样轮到下一次时，就放到前面
}
return b;
}
相应的测试代码是这样的：
@Test
public void testCountSort() {
Random rand = new Random();
int n = 5000000;
int k = 10;
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = rand.nextInt(k);
}
assertFalse(isSorted(a));
int[] b = countSort(a, k);
assertTrue(isSorted(b));
}
从代码中可以看出，计数排序的复杂次为 ⊙(n), 是稳定排序，要使用同样多的内存空间
趁热打铁， 基数排序
直接上代码
int[] radixSort(int[] a, int d) { // 数据a中的数字不会长于d位
for (int i = 0; i < d; i++) {
a = stableSort(a, i); // 从最右边开始，一位一位排
}
return a;
}
stableSort 怎么样呢？ 我们使用上面的计数排序， 稍微进行小调整
int[] stableSort(int[] a, int k) { // 对a数组中的数的第k位进行计数排序
int[] c = new int[10]; // 数在[0， 10]
for (int i = 0; i < c.length; ++i) {
c[i] = 0;
}
for (int i = 0, n = a.length; i < n; i++) {
int d = getIndex(a[i], k);
c[d]++; // 统计第k位数
}
for (int i = 1; i < c.length; i++) {
c[i] = c[i] + c[i - 1];
}
int[] b = new int[a.length];
for (int i = a.length - 1; i >= 0; i--) {
int d = getIndex(a[i], k);
b[c[d] - 1] = a[i];
c[d]--;
}
return b;
}
getIndext很简单， 大学C语言经常做的，截取指定位数值
int getIndex(int a, int k) {
while (a != 0 && k != 0) {
a /= 10;
k--;
}
return a % 10;
}
最后还是测试，Test Test, 没有Test就是nothing!!
@Test
public void testRadixSort() {
Random rand = new Random();
int[] a = new int[100000]; // 一百万个
for (int i = 0; i < a.length; i++) {
a[i] = rand.nextInt(10000000); // 不大于7位数
}
int[] b = radixSort(a, 7);
assertTrue(isSorted(b));
}
因为 基数排序 要经过d (数据长度)次排序， 每次使用计数排序， 计数排序的复杂度为 ⊙(n), d 相当于常量，和N无关， 所以基数排序也是 ⊙(n)
基数排序虽然是线性复杂度， 即对n个数字处理了n次，但是每一次代价都比较高， 而且使用计数排序的基数排序不能进行原地排序，需要更多的内存， 并且快速排序可能更好地利用硬件的缓存， 所以比较起来，像快速排序这些原地排序算法更可取。
但是基数排序有个优点是：它是稳定的(PS: 归并排序也是稳定的）
继续打铁， 桶排序
把一堆数据快速地扔进有序桶中，再对桶中的数据进行排序...
float[] bucketSort(float a[]) { // 0 < a[i] < 1，且分布较均匀
int n = a.length;
List[] lists = new List[n]; // 准备好n个桶
for (int i = 0; i < n; i++) {
lists[i] = new ArrayList();
}
for (int i = 0; i < n; i++) { // 把每个数据放到相应的桶
lists[(int)(n * a[i])].add(a[i]);
}
for (int i = 0; i < n; i++) { // 现在每个桶中平均有一个数据
insertionSort(lists[i]); // 对它进行一次插入排序
}
float b[] = new float[n]; // 输出
int k = 0;
for (int i = 0; i < n; i++) {
List list = lists[i];
for (int j = 0; j < list.size(); j++) {
b[k++] = (Float) list.get(j);
}
}
return b;
}
void insertionSort(List list) {
for (int i = 1; i < list.size(); i++) {
float t = (Float) list.get(i);
int j = i - 1;
while (j >= 0 && (Float)list.get(j) > t) {
list.set(j + 1, list.get(j));
j--;
}
list.set(j + 1, t);
}
}
最后还是测试：
@Test
public void testBucketSort() {
Random rand = new Random();
float[] a = new float[1000];
for (int i = 0; i < a.length; i++) {
a[i] = rand.nextFloat();
}
float[] b = bucketSort(a);
assertTrue(isSorted(b));
}
对了，这里还有一个isSorted
原先的方法是针对int[] 的，现在是float[], 所以要重写一个， 仅仅这个参数不一样
问： 在java中这样的可以泛形吗？
public static boolean isSorted(int[] ary) {
for (int i = 0; i < ary.length - 1; i++) {
if (ary[i] > ary[i + 1]) {
return false;
}
}
return true;
}
public static boolean isSorted(float[] ary) {
for (int i = 0; i < ary.length - 1; i++) {
if (ary[i] > ary[i + 1]) {
return false;
}
}
return true;
}
对java中的泛形仅仅停留在collection的使用上
对于c++，泛形的作用主要在于code generation， 而java中的擦除法泛形更多的功能是type check。
对java的泛形没有多作研究，不知道是否这样。
其实程序员不是很需要type check的，因为类型错误肯定会在test中给检测出来，而且我们也是思考着写程序的，几乎很少把类型给弄错了。当然强类型在编译优化，效率上肯定有一定的用处。但是我需要敲更少的键盘做更多的事。
啊呀，说算法，扯远了。
最后还有桶排序的复杂度没有说明。
桶排序的其它几个循环很清楚，都是线性的，主要是看下面这个循环:
for (int i = 0; i < n; i++) { // 现在每个桶中平均有一个数据
insertionSort(lists[i]); // 对它进行一次插入排序
}
虽然 insertionSort 是平方复杂度的， 但是 lists[i] 的数据是不会随着 n 的增长而增长的。 如果有n桶，桶中平均只有一个数。
所以上面这个循环也是线性复杂度的
所以桶排序的复杂度也是线性的
分享到：
相关推荐
麻省理工算法导论全套笔记 ，英文版，看好再下哦。
我做的算法导论读书笔记。请大家提供意见和建议，也欢迎大家一起交流。
MIT算法导论公开课之课程笔记 5.线性时间排序.rar
我做的算法导论读书笔记,这是第三个了。请大家提供意见和建议，也欢迎大家一起交流。 关于该系列读书笔记的详情和进展请看我的博客http://blog.csdn.net/PowerRock
线性时间排序 以下为本人整理课程笔记 课程地址：b站搬运 github：还有除了算法导论外一些基础知识的笔记 我们能做到的排序有多快？ 速度取决于计算模型【哪些操作是被允许的】 比较排序的算法模型 在模型中只能进行...
《算法导论》读书笔记_附录A习题解答 学习C C++ 资料
算法导论读书笔记，整理别人的，不算抄袭吧。。
算法导论 学习笔记
从第二到第八章的总结
算法导论大作业：股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业：股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业：股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业...
麻省理工的关于算法导论的笔记，英文版 希望对学习算法导论的朋友能有帮助
排序算法的讲述。有关线性排序算法的讲述。
更多内容请关注http://blog.csdn.net/PowerRock/
山东大学软件学院算法导论课程的复习笔记。文件里面包含了五份笔记，涵盖BFS、DFS、SCC、Topological、MST、ShortestPath、maxflow。主要是对PPT的内容的整理概括。个人整理不易，其中的图片都是自己绘制的，就是...
算法导论课堂笔记。 英文版。 Word文档。
中科大软件学院 算法导论课程实验 正式题目一 常见排序算法的实现与性能比较 实验报告 包括合并排序、插入排序、希尔排序、快速排序、冒泡排序、桶排序
麻省理工学院算法导论_笔记 算法导论，学习计算机必备
算法作业的线性选择排序 算法作业的线性选择排序 算法作业的线性选择排序
包括麻省理工学院算法课的教材《算法导论》中英文版，麻省理工的课堂讲义，练习，以及课后答案，值得学习算法的学生研究。
算法导论讲义\算法导论讲义 算法导论讲义\算法导论讲义 算法导论讲义\算法导论讲义 MIT教师的课堂讲义 很有价值