8-线性时间排序-算法导论

算法导论-chapter 8 -线性时间排序

渐进记号

注：以后的笔记中 上下界一律用F(.)表示

比较排序

通过比较元素大小排序

例如:堆排序，归并排序，快速排序

可抽象为一个决策树模型（是完全二叉树）

定理

最坏情况下，任何比较排序都需要做大omiga( nlgn )次比较

计数排序

基本思想

对于输入的元素x，确定小于它的元素个数，然后将x放到它在输出数组中的位置

根据上一步结果，将A中元素放入输出数组B中对应位置:

时耗

F(k+n)——即：关于k+n的上下界

优于比较排序的上界 大omiga( nlgn )

一般当 k=O(n)时，推荐采用计数排序

基数排序

基本思路：将元素从个位开始对齐，然后比较个位元素并据此排序—转十位并排序—...—输出结果

根据第i位的数值大小排序， i=1 to d

时间复杂度

若给定n个位数，每一数位有k个可能取值。 如果采用稳定的排序算法F(n+k)，则时耗为 F( d(n+k) )

选择适当的排序算法做基数排序时，尽管基数排序的平均时耗可以控制在F(n)，但是它真不一定比快速排序快（因为它的F(n)常数项比较大）

桶排序

前提：假定输入数据服从均匀分布

基本思路

注意：将遍历输入数组A以放入桶的过程相当于对A进行了一个分层操作，每一个桶里存放的数据一定是在桶的大小范围内的

算法：Bucket-Sort(A)

将B[i]初始化为空链表

将A[i] 插入到 B[ nA[i] ]处， i=1 to n

时耗：F(n)

此方法稳定，比快速排序还要快，但是空间复杂度非常高

注意：即使输入不服从均匀分布，但满足所有桶的大小平方和与总的元素呈线性关系，那么桶排序仍然可以在线性时间内完成