资源描述：
《线性时间的排序ch8》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、算法设计与分析算法设计与分析DesignandAnalysisofAlgorithmsDesignandAnalysisofAlgorithmsDesignandAnalysisofAlgorithms主讲人主讲人徐徐云云FallFall2010,2010,USTCUSTCPart1FoundationPart2SortingandOrderStatisticschap6Heapsortchap7Quicksortchap8SortinginLinearTimechap9MediansandOrderStatisticsPart3DataSt
2、ructurePart4AdvancedDesignandAnalysisTechniquesPart5AdvancedDataStructuresPart6GraphAlgorithmsPart7SelectedTopicsPart8Supplement第第88章章线性时间的排序线性时间的排序8.18.1排序的下界排序的下界8.28.2计数排序计数排序8.38.3基数排序基数排序8.48.4桶排序桶排序8.1排序的下界ò判定树模型ò最坏情形的下界2010-10-4算法设计与分析4判定树模型ò任何n个元素a,a,…,a的基于比较的排序可以用一
3、颗二12n叉排序树表示，其叶子节点代表一类输入实例的排序结果。ò示例：a=6,a=8,a=5其判定树如下1231:2≤＞2:31:3≤＞＞≤<1,2,3>1:3<2,1,3>2:3≤＞≤＞<1,3,2><3,1,2><2,3,1><3,2,1>该实例的比较路径由箭头所示，叶子节点代表的是排序结果。2010-10-4算法设计与分析5最坏情形的下界ò定理8.1基于比较排序算法在最坏情形下，需要Ω(nlogn)。ò证明：设h,l分别代表判定树的高度和叶子数∵判定树是一颗二叉树∴l≤2h//叶子数不超过2h∴n!≤l≤2h//n!为排序的结果数于是有
4、，h≥logn!≥Ω(nlogn)证毕！2010-10-4算法设计与分析6第第88章章线性时间的排序线性时间的排序8.18.1排序的下界排序的下界8.28.2计数排序计数排序8.38.3基数排序基数排序8.48.4桶排序桶排序8.2计数排序ò基本思想ò一种特殊情形的计数排序ò一般情形的计数排序2010-10-4算法设计与分析8基本思想ò统计小于或等于A[i]的元素数目，将A[i]置入相应的位置，即A[i]ÆB[小于或等于A[i]的元素数目]ò主要要解决的问题：¾计数：统计小于或等于A[i]的元素数目¾值相同元素的处理2010-10-4算法设计
5、与分析9一种特殊情形的计数排序ò问题：n个互不相同的整数A[1..n]，1≤A[i]≤ni=1~nò排序算法：SpecialCountingSort(A,B){//B[1..n]为排序结果fori←1tondoB[A[i]]←A[i];//如A[i]=5，就放到B[5]中}时间：O(n)，无比较2010-10-4算法设计与分析10一般情形的计数排序（1）ò问题：n个可以相同的整数A[1..n]，1≤A[i]≤k，i=1~n，这里k是A[i]的取值范围，不一定为n。ò基本思想：步骤：A[1..n]→计数器C[1..k]→B[1..n]¾Step
6、1(值相同元素的计数)：将A中的值为i的元素个数记入C[i]中；¾Step2(累计计数)：对C[1..k]进行修改，使得C[i]的值表示为≤i的元素个数；¾Step3(放置)：将A[j]依据C[A[j]]，放入正确位置B[C[A[j]]]上，并修改C[A[j]]←C[A[j]]-1；2010-10-4算法设计与分析11一般情形的计数排序（2）ò算法：CountingSort(A,B,k){//B[1..n]为排序结果，C[1..k]为计数数组fori←1tokdoC[i]←0;forj←1tolength[A]do//扫描A，值相同元素计数C
7、[A[j]]++;fori←2tokdo//C[i]修改，累计计数C[i]←C[i]+C[i-1];forj←length[A]downto1do{B[C[A[j]]]←A[j];C[A[j]]--;}}时间：T(n,k)=θ(n+k)=θ(n)，如果k=θ(n)时2010-10-4算法设计与分析12第第88章章线性时间的排序线性时间的排序8.18.1排序的下界排序的下界8.28.2计数排序计数排序8.38.3基数排序基数排序8.48.4桶排序桶排序8.3基数排序ò算法ò一些讨论2010-10-4算法设计与分析14基数排序算法ò假定A[1..
8、n]是非负整数，用k进制表示为不超过d位数。ò算法：RadixSort(A,d){fori←1toddo使用稳定的排序算法对A的第i位排序；//如计数排序}ò时间：
