《算法导论》第8章 线性时间排序.pptx

线性时间排序

排序算法的复杂度快速排序快排平均复杂度O(nlgn)快排最坏情况复杂度O(n2)堆排序永远是O(nlgn)归并排序也是O(nlgn)插入排序O(n2)所有这些排序都没有低于nlgn的，那么问题来了，运行时间可能小于nlgn吗？

答案是看情况前面提到的快速排序，归并排序，堆排序，插入排序都是基于比较模型的，在比较模型中，nlgn是最快的。如果不基于比较模型，可以比nlgn快，最快能到O(n)，但不基于比较模型的排序算法，对输入数据的类型和范围会有限制。

比较排序的算法模型在比较排序模型中，你只能做比较操作：小于，大于，小于等于，大于等于和等于来决定元素的相对顺序。这是这个算法的局限，在某种意义上也说明了要处理的元素类型，这些元素是可以进行比较操作的。接下来我们会证明这个定理：比较排序的算法运算速度不会快于nlgn。首先我们来看一下比较模型，尝试去理解为什么在只允许比较操作时最少需要nlgn次操作。

决策树

比较排序下限证明

排序的下限不限于比较排序，排序的复杂度下限是O(n)，因为n个元素你至少都要遍历一次。假设是特定范围内的整数，我们会利用这点来在线性时间内排序。

计数排序

计数排序伪代码

桶排序

桶排序伪代码

谢谢！