第8章线性时间排序算法分析与设计杭电褚一平.ppt
《第8章线性时间排序算法分析与设计杭电褚一平.ppt》由会员分享,可在线阅读,更多相关《第8章线性时间排序算法分析与设计杭电褚一平.ppt(27页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、20 五月 2023第8 章线性时间排序算法分析与设计杭电褚一平2本章内容介绍了几种O(nlgn)的排序算法:合并排序和堆排序达到此上界;快速排序平均情况下达到此上界;比较排序算法的下界线性时间排序:计数排序(Counting Sort)基数排序(Radix Sort)桶排序(Bucket Sort)38.1 排序算法的下界比较排序算法的作用比较排序算法仅用来确定输入序列 的元素间次序,即给定两个元素ai和aj,测试ai aj 中哪一个成立。48.1 排序算法的下界决策树模型比较排序可以被抽象的视为决策树。一棵决策树是一棵满二叉树,表示某排序算法作用于给定输入所做的所有比较。(6,8,5)5决
2、策树在决策树中,对每个内结点都注明i:j,其中1i,jn,n是输入序列中的元素个数。对每个叶结点都注明排列(1),(2),(n)。排序算法的执行对应于遍历一条从树的根到叶结点的路径。在每个内节结点处要做比较要使排序算法能正确的工作,其必要条件是,n个元素的n!种排列中的每一种都要作为决策树的一个叶子而出现。ai a j6最坏情况下界在决策树中,从根到任意一个可达叶节点之间最长路径的长度,表示对应的排序算法中最坏情况下的比较次数。这样,一个比较排序算法中的最坏情况比较次数就与其决策树的高度相等。定理8.1 任意一个比较排序算法在最坏情况下,都需要(nlgn)次的比较。于2,则有n!l 2定理8.
3、1的证明证明:对于一棵每个排列都作为一个可达叶结点出现的决策树,根据前面的讨论即可确定其高度。考虑一棵高度为h的、具有l 个可达叶结点的决策树,它对应于对n个元素所做的比较排序。因为n个输入元素共有n!种排列,每一种都作为一个叶子出现在树中,故有n!l。又由于在一棵高为h的二叉树中,叶子的数目不多对该式取对数,得到hlg(n!)=(nlgn)推论8.2堆排序和归并排序是渐进最优的比较算法证明:堆排序和归并排序的运行时间上界O(nlgn)与定理8.1给出的最坏情况下界(nlgn)一致7hh88.2 计数排序计数排序假设n个输入元素中的每一个都是介于0到k之间的整数,此处k为某个整数,当k=O(n
4、)时,技术排序的运行时间是O(n)。计数排序的基本思想就是对每一个输入元素x,确定出小于x的元素个数。有了这一信息,就可以 把x直接放到它在最终输出数组中的位置上。在计数排序算法中,我们假设输入时隔数组A1.n,length(A)=n。另外还需要两个数组:存放排序结果的B1.n,以及提供临时存数区的C1.k9计数排序程序COUNT-SORT(A,B,k)1 for i0 to k2 do Ci03 for j1 to lengthA4 do CAj CAj+15 Ci 现在包含等于i 的元素个数6for i 1 to k7 do Ci Ci+Ci-18 Ci 现在包含小于或等于i 的元素个数7
5、 for j lengthA downto 18 do BCAj Aj9 CAj CAj-110计数排序过程1211计数排序过程3412计数排序过程56算法说明在第9-11 行中的for 循环部分,把每个元素Aj 放在输出数组B 中与其相应的最终位置上。如果所有n个元素都不相同,则当第一次执行到第9行时,对每个Aj,值CAj 即为Aj 在输出数组中的最终正确位置,因为共有CAj 个元素小于等于Aj。由于各个元素可能不一定是不同的,因此,每当将一个值Aj 放入数组B 中时,都要减少CAj 的值。这会使得下一个其值等于Aj 的输入元素(如果存在的话)直接进入数组B 中Aj 的前一个位置上14计数排
6、序时间代价计数排序时间代价算法第12 行的for 循环所花时间为(k)。第34 行中for 循环所花时间为(n),第67 行for 循环所花时间为(k),第911 行的for 循环所花时间为(n)。这样,总的时间就是(k+n)。实践中,当k=O(n)时,运行时间为O(n)。计数排序的特点计数排序算法没有用到元素间的比较,它利用元素的实际值来确定它们在输出数组中的位置,不是一个基于比较的排序算法,从而它的计算时间下界不再是(nlogn)由于算法第4行使用了downto语句,经计数排序,输出序列中值相同的元素之间的相对次序与他们在输入序列中的相对次序相同,因此计数排序算法是一个稳定的排序算法。在卫
7、星数据排序和基数排序中间应用。158.3 基数排序基数排序(radix sort)是一种用在老式穿卡机上的算法。一张卡片有80列,每列可在12个位置中的任一处穿孔。排序器可被机械地“程序化”以检查每一迭卡片中的某一列,再根据穿孔的位置将它们分放12个盒子里。这样,操作员就可逐个地把它们收集起来。其中第一个位置穿孔的放在最上面,第二个位置穿孔的其次,等等。对十进制数字来说,每列中只用到10个位置(另两个位置用于编码非数值字符)。一个d位数占用d个列。因为卡片排序器一次只能查看一个列,要对n张片上的d位数进行排序就要有个排序算法。直觉上,大家可能觉得应该按最重要的一位排序,然后对每个盒子中的数递归
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性 时间 排序 算法 分析 设计 杭电褚一平
限制150内