8-线性时间排序-算法导论
2016-06-02 21:33:09 5 举报AI智能生成
算法导论-8-线性时间排序算法-个人笔记
作者其他创作
大纲/内容
渐进记号
大omiga , *, 大O——依次表示渐进下界，上下界，上界
注：以后的笔记中 上下界一律用F(.)表示
比较排序
通过比较元素大小排序
例如:堆排序，归并排序，快速排序
可抽象为一个决策树模型（是完全二叉树）
定理
最坏情况下，任何比较排序都需要做大omiga( nlgn )次比较
计数排序
基本思想
对于输入的元素x，确定小于它的元素个数，然后将x放到它在输出数组中的位置
算法: Counting-Sort(A,B,k)
令C[0,...,k]为新数组并初始化为零
对A中相同元素个数进行计数： C[ A[j] ] = C[ A[j] ] + 1, j=1 to A.length
对A中每一个元素，计算小于该元素的元素个数：C[i] = C[i] + C[i-1], i=1 to k
根据上一步结果，将A中元素放入输出数组B中对应位置:
时耗
F(k+n)——即：关于k+n的上下界
优于比较排序的上界 大omiga( nlgn )
一般当 k=O(n)时，推荐采用计数排序
基数排序
基本思路：将元素从个位开始对齐，然后比较个位元素并据此排序—>转十位并排序—>...—>输出结果
算法：Radix-Sort( A,d )
根据第i位的数值大小排序， i=1 to d
时间复杂度
若给定n个位数，每一数位有k个可能取值。 如果采用稳定的排序算法F(n+k)，则时耗为 F( d(n+k) )
选择适当的排序算法做基数排序时，尽管基数排序的平均时耗可以控制在F(n)，但是它真不一定比快速排序快（因为它的F(n)常数项比较大）
桶排序
前提：假定输入数据服从均匀分布
基本思路
将[0,1)划分为n个相同大小的子区间，称为桶，然后将数据放入各桶中；
因为数据是[0,1)上的 均匀分布，所以一般不会只落入一个桶，此时对各个桶分布进行排序，然后遍历各个桶给出最终结果
注意：将遍历输入数组A以放入桶的过程相当于对A进行了一个分层操作，每一个桶里存放的数据一定是在桶的大小范围内的
算法：Bucket-Sort(A)
记n=A.length; 定义新数组B[1,...,n-1]
将B[i]初始化为空链表
将A[i] 插入到 B[ nA[i] ]处， i=1 to n
用插入排序排列链表B[i], i=0 to n-1
遍历B[0],...,B[n-1]以便把结果放在一起得出最中排列结果
时耗：F(n)
此方法稳定，比快速排序还要快，但是空间复杂度非常高
注意：即使输入不服从均匀分布，但满足所有桶的大小平方和与总的元素呈线性关系，那么桶排序仍然可以在线性时间内完成
职业：暂无
0 条评论
下一页
