

首页  思维导图  详情



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)

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

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

 Collect

Get Started

排序算法

 Collect

Get Started

数据结构与算法

 Collect

Get Started

排序算法编程方法总结

 Collect

Get Started

排序算法总结





0 条评论

下一页