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

1、算法设计与分析算法设计与分析谭守标谭守标安徽大学安徽大学 电子学院电子学院2019.9第七章第七章 线性时间排序线性时间排序n排序算法的下界排序算法的下界n计数排序过程及分析计数排序过程及分析n基数排序基数排序n桶排序过程及分析桶排序过程及分析n程序演示及阐明程序演示及阐明排序算法的下界排序算法的下界n决策树决策树n最坏情况下界最坏情况下界n定理定理9.19.1n推论推论9.29.2决策树决策树n决策树表示了某种排序算法作用于给定输入上所做的一切比较,而控制构造,数据挪动等那么被忽略。 最坏情况下界最坏情况下界n 在决策树中在决策树中, ,由根到任一叶节点间最由根到任一叶节点间最长途径的长度表

2、示了对应的排序算法中长途径的长度表示了对应的排序算法中最坏情况比较次数。这样最坏情况比较次数。这样, , 一个比较排序一个比较排序算法中的最坏情况比较次数就与其决策算法中的最坏情况比较次数就与其决策树的高度对应树的高度对应, , 同时关于其决策树高度的同时关于其决策树高度的下界也就是关于比较排序算法运转时间下界也就是关于比较排序算法运转时间的下界。的下界。 定理定理9.19.1n定理:恣意一棵对n个元素排序的决策树有高度 (nlgn) 。 n证明: 思索对n个元素排序的, 高度为h的决策树。由于n!种陈列, 每种陈列代表一种不同的最终排序, 故该树必需至少有n!片叶子。又一颗高度为h的二叉树的

3、叶子数不多于2h, 那么:n n! 2hn两边取对数, 有:n h lg(n!)定理定理9.19.1n由于由于lg lg函数是单调递增的函数是单调递增的, , 又根据又根据StirlingStirling近似公式近似公式, , 有有: :n n! (n/e)n n! (n/e)nn所以所以, , 有有: :n h lg(n/e)n h lg(n/e)nn = nlgn = nlgn nlge nlge n = (nlgn) = (nlgn)推论推论9.29.2n推论推论: : 堆排序和合并排序是渐进最优的堆排序和合并排序是渐进最优的比较算法。比较算法。n 证明证明: :堆排序和合并排序的运转时

4、间上堆排序和合并排序的运转时间上界界O(nlgn)O(nlgn)与定理与定理9.19.1给出的最坏情况下给出的最坏情况下界界 (nlgn) (nlgn)一致。一致。 计数排序过程及分析计数排序过程及分析n计数排序思绪计数排序思绪n计数排序算法计数排序算法n计数排序分析计数排序分析计数排序思绪计数排序思绪n计数排序假设计数排序假设n n个输入中的每一个都是介个输入中的每一个都是介于于1 1到到k k之间的整数之间的整数, , 此处此处k k是整数。是整数。n计数排序的根本思想就是对每一个元素计数排序的根本思想就是对每一个元素x, x,确定出小于确定出小于x x的元素数。有了这个信息就的元素数。有

5、了这个信息就可把可把x x直接放到它在最终输出数组中的位直接放到它在最终输出数组中的位置上。例如有置上。例如有1717个元素小于个元素小于x, x,那么那么x x就属就属于第于第1818个输出位置。个输出位置。n假设有相等的元素怎样办？假设有相等的元素怎样办？计数排序算法计数排序算法nCOUNTING_SORT(A, B, k)COUNTING_SORT(A, B, k)n1 for i 1 to k1 for i 1 to kn2 do Ci 02 do Ci 0n3 for j 1 to lengthA3 for j 1 to lengthAn4 do CAj CAj+14 do CAj

6、CAj+1n5 Ci5 Ci如今包含等于如今包含等于i i的元素个数的元素个数n6 for i 2 to k6 for i 2 to kn7 do Ci Ci+Ci-17 do Ci Ci+Ci-1n8 Ci8 Ci如今包含小于等于如今包含小于等于i i的元素个数的元素个数n9 for j lengthA downto 19 for j lengthA downto 1n10 do BCAj Aj10 do BCAj Ajn11 CAj CAj-111 CAj CAj-1计数排序算法计数排序算法计数排序分析计数排序分析n计数排序的时间分析计数排序的时间分析, , 第第1-21-2行的行的for

7、for循环循环破费的时间为破费的时间为O(k), O(k), 第第3-43-4行中行中forfor循环所循环所破费时间为破费时间为O(n),O(n),第第6-76-7行的行的forfor循环破费循环破费的时间为的时间为O(k)O(k)。这样，总的时间就是。这样，总的时间就是O(k+n)O(k+n)。在实际中，当。在实际中，当k= O(n)k= O(n)时，我时，我们经常采用计数排序，这时其运转时间们经常采用计数排序，这时其运转时间为为O(n)O(n)。基数排序过程及分析基数排序过程及分析n基数排序思想基数排序思想n基数排序算法基数排序算法n基数排序分析基数排序分析 基数排序思想基数排序思想n每

8、种数字数据都是一种进位计数制数据，每种数字数据都是一种进位计数制数据，如二进制、十进制等，每一位的取值范如二进制、十进制等，每一位的取值范围即基数。围即基数。n基数排序的思想就是在某种进制下对一基数排序的思想就是在某种进制下对一切数据从低位到高位逐位进展排序，最切数据从低位到高位逐位进展排序，最终就能得到整体排序的结果。终就能得到整体排序的结果。基数排序算法基数排序算法基数排序算法基数排序算法nRADIX_SORT(A, d)RADIX_SORT(A, d)n1 for i 1 to d1 for i 1 to dn2 do 2 do 运用一种稳定的排序方法来对运用一种稳定的排序方法来对n 数

9、组数组A A按第按第i i位数字进展排序位数字进展排序基数排序分析基数排序分析n正确性：归纳证明正确性：归纳证明n时间代价：时间代价：n当每位数字都介于当每位数字都介于1-k1-k之间，且之间，且k k不太大时，不太大时，可以选择计数排序。可以选择计数排序。n每一位上的处置时间为：每一位上的处置时间为： (n+k) (n+k) n总时间为：总时间为： (d(n+k) (d(n+k)， 当当d d为常量，为常量，k= k= (n) (n)时，时， (d(n+k)= (d(n+k)= (n) (n)基数排序例基数排序例n以一个计算机字以一个计算机字(16(16位位) )为基数，一个为基数，一个64

10、64位数那么为位数那么为4 4位数，即位数，即d=4d=4， k=216 k=216，用基数排序只需用基数排序只需4 4次。次。桶排序过程及分析桶排序过程及分析n桶排序思想桶排序思想n桶排序算法桶排序算法n桶排序分析桶排序分析 桶排序思想桶排序思想n 桶排序的思想就是把区间桶排序的思想就是把区间0, 1)0, 1)划分划分成成n n个一样大小的子区间个一样大小的子区间, , 或称桶或称桶, , 然后将然后将n n个输入数分布到各个桶中去。假设输入个输入数分布到各个桶中去。假设输入数均匀分布在数均匀分布在0, 1)0, 1)上上, , 那么普通不会有很那么普通不会有很多数落在一个桶中。为得到结果

11、多数落在一个桶中。为得到结果, , 先对各先对各个桶中的数进展排序个桶中的数进展排序, , 然后按次序把各个然后按次序把各个桶中的元素列出来即可。桶中的元素列出来即可。桶排序算法桶排序算法nBUCKET_SORT(A)BUCKET_SORT(A)n1 n lengthA1 n lengthAn2 for i 1 to n2 for i 1 to nn3 do 3 do 将将AiAi插入到表插入到表B B nAinAi n4 for i 0 to n-14 for i 0 to n-1n5 do 5 do 用插入排序对表用插入排序对表BiBi进展排序进展排序n6 6 将表将表B0, B1, .,

12、 Bn-1B0, B1, ., Bn-1按顺序合并按顺序合并桶排序算法桶排序算法桶排序分析桶排序分析n正确性：反证法正确性：反证法n时间代价：时间代价：桶排序分析桶排序分析排序算法稳定性排序算法稳定性n假设待排序的序列中，存在多个具有一假设待排序的序列中，存在多个具有一样值的元素，经过排序，这些元素的相样值的元素，经过排序，这些元素的相对次序坚持不变，那么称该算法是稳定对次序坚持不变，那么称该算法是稳定的；假设经排序后，元素的相对的；假设经排序后，元素的相对 次序发次序发生了改动，那么称该算法是不稳定的。生了改动，那么称该算法是不稳定的。 常见排序算法的稳定性常见排序算法的稳定性n堆排序算法堆排序算法 不稳定不稳定n快速排序算法快速排序算法 不稳定不稳定n归并排序算法归并排序算法