算法设计与分析线性时间排序.ppt

算法设计与分析,谭守标 安徽大学 电子学院 2007.9,第七章 线性时间排序,排序算法的下界 计数排序（过程及分析） 基数排序 桶排序（过程及分析） 程序演示及说明,排序算法的下界,决策树 最坏情况下界 定理9.1 推论9.2,决策树,决策树表示了某种排序算法作用于给定输入上所做的所有比较,而控制结构,数据移动等则被忽略。,最坏情况下界,在决策树中,由根到任一叶节点间最长路径的长度表示了对应的排序算法中最坏情况比较次数。这样, 一个比较排序算法中的最坏情况比较次数就与其决策树的高度对应, 同时关于其决策树高度的下界也就是关于比较排序算法运行时间的下界。,定理9.1,定理:任意一棵对n个元素排序的决策树有高度 (nlgn) 。 证明: 考虑对n个元素排序的, 高度为h的决策树。因为n!种排列, 每种排列代表一种不同的最终排序, 故该树必须至少有n!片叶子。又一颗高度为h的二叉树的叶子数不多于2h, 则: n! 2h 两边取对数, 有: h lg(n!),定理9.1,因为lg函数是单调递增的, 又根据Stirling近似公式, 有: n! (n/e)n 所以, 有: h lg(n/e)n = nlgn nlge = (nlgn),推论9.2,推论: 堆排序和合并排序是渐进最优的比较算法。 证明:堆排序和合并排序的运行时间上界O(nlgn)与定理9.1给出的最坏情况下界 (nlgn)一致。,计数排序（过程及分析）,计数排序思路 计数排序算法 计数排序分析,计数排序思路,计数排序假设n个输入中的每一个都是介于1到k之间的整数, 此处k是整数。 计数排序的基本思想就是对每一个元素x,确定出小于x的元素数。有了这个信息就可把x直接放到它在最终输出数组中的位置上。例如有17个元素小于x,则x就属于第18个输出位置。 如果有相等的元素怎么办？,计数排序算法,COUNTING_SORT(A, B, k) 1 for i 1 to k 2 do Ci 0 3 for j 1 to lengthA 4 do CAj CAj+1 5 Ci现在包含等于i的元素个数 6 for i 2 to k 7 do Ci Ci+Ci-1 8 Ci现在包含小于等于i的元素个数 9 for j lengthA downto 1 10 do BCAj Aj 11 CAj CAj-1,计数排序算法,计数排序分析,计数排序的时间分析, 第1-2行的for循环花费的时间为O(k), 第3-4行中for循环所花费时间为O(n),第6-7行的for循环花费的时间为O(k)。这样，总的时间就是O(k+n)。在实践中，当k= O(n)时，我们常常采用计数排序，这时其运行时间为O(n)。,基数排序（过程及分析）,基数排序思想 基数排序算法 基数排序分析,基数排序思想,每种数字数据都是一种进位计数制数据，如二进制、十进制等，每一位的取值范围即基数。 基数排序的思想就是在某种进制下对所有数据从低位到高位逐位进行排序，最终就能得到整体排序的结果。,基数排序算法,基数排序算法,RADIX_SORT(A, d) 1 for i 1 to d 2 do 使用一种稳定的排序方法来对 数组A按第i位数字进行排序,基数排序分析,正确性：归纳证明 时间代价： 当每位数字都介于1-k之间，且k不太大时，可以选择计数排序。 每一位上的处理时间为： (n+k) 总时间为： (d(n+k)， 当d为常量，k= (n)时， (d(n+k)= (n),基数排序例,以一个计算机字(16位)为基数，一个64位数则为4位数，即d=4， k=216，用基数排序只需4次。,桶排序（过程及分析）,桶排序思想 桶排序算法 桶排序分析,桶排序思想,桶排序的思想就是把区间0, 1)划分成n个相同大小的子区间, 或称桶, 然后将n个输入数分布到各个桶中去。如果输入数均匀分布在0, 1)上, 则一般不会有很多数落在一个桶中。为得到结果, 先对各个桶中的数进行排序, 然后按次序把各个桶中的元素列出来即可。,桶排序算法,BUCKET_SORT(A) 1 n lengthA 2 for i 1 to n 3 do 将Ai插入到表B nAi 4 for i 0 to n-1 5 do 用插入排序对表Bi进行排序 6 将表B0, B1, ., Bn-1按顺序合并,桶排序算法,桶排序分析,正确性：反证法 时间代价：,桶排序分析,排序算法稳定性,若待排序的序列中，存在多个具有相同值的元素，经过排序，这些元素的相对次序保持不变，则称该算法是稳定的；若经排序后，元素的相对 次序发生了改变，则称该算法是不稳定的。,常见排序算法的稳定性,堆排序算法 不稳定 快速排序算法 不稳定 归并排序算法 稳