算法设计与分析线性时间排序.ppt
算法设计与分析线性时间排序 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第七章第七章 线性时间排序线性时间排序n排序算法的下界排序算法的下界n计数排序（过程及分析）计数排序（过程及分析）n基数排序基数排序n桶排序（过程及分析）桶排序（过程及分析）n程序演示及说明程序演示及说明排序算法的下界排序算法的下界n决策树决策树n最坏情况下界最坏情况下界n定理定理9.19.1n推论推论9.29.2决策树决策树n决策树表示了某种排序算法作用于给定输入上决策树表示了某种排序算法作用于给定输入上所做的所有比较所做的所有比较,而控制结构而控制结构,数据移动等则被数据移动等则被忽略。忽略。最坏情况下界最坏情况下界n 在决策树中在决策树中,由根到任一叶节点间最由根到任一叶节点间最长路径的长度表示了对应的排序算法中长路径的长度表示了对应的排序算法中最坏情况比较次数。这样最坏情况比较次数。这样,一个比较排序一个比较排序算法中的最坏情况比较次数就与其决策算法中的最坏情况比较次数就与其决策树的高度对应树的高度对应,同时关于其决策树高度的同时关于其决策树高度的下界也就是关于比较排序算法运行时间下界也就是关于比较排序算法运行时间的下界。的下界。定理定理9.19.1n定理定理:任意一棵对任意一棵对n n个元素排序的决策树有高度个元素排序的决策树有高度(nlgn)(nlgn)。n证明证明:考虑对考虑对n n个元素排序的个元素排序的,高度为高度为h h的决策树。的决策树。因为因为n!n!种排列种排列,每种排列代表一种不同的最终排每种排列代表一种不同的最终排序序,故该树必须至少有故该树必须至少有n!n!片叶子。又一颗高度为片叶子。又一颗高度为h h的二叉树的叶子数不多于的二叉树的叶子数不多于2h,2h,则则:n n!2h n!2hn两边取对数两边取对数,有有:n h lg(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 证明证明:堆排序和合并排序的运行时间上堆排序和合并排序的运行时间上界界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的元素数。有了这个信息就的元素数。有了这个信息就可把可把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 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行的行的forfor循环循环花费的时间为花费的时间为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每种数字数据都是一种进位计数制数据，每种数字数据都是一种进位计数制数据，如二进制、十进制等，每一位的取值范如二进制、十进制等，每一位的取值范围即基数。围即基数。n基数基数排序排序的思想就是在某种进制下对所的思想就是在某种进制下对所有数据有数据从低位到高位从低位到高位逐位进行排序，最逐位进行排序，最终就能得到整体排序的结果。终就能得到整体排序的结果。基数排序算法基数排序算法基数排序算法基数排序算法nRADIX_SORT(A,d)RADIX_SORT(A,d)n1 for i 1 to d1 for i 1 to dn2 do 2 do 使用一种稳定的排序方法来对使用一种稳定的排序方法来对 数组数组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位位)为基数，一个为基数，一个6464位位数则为数则为4 4位数，即位数，即d=4d=4，k=216k=216，用基，用基数排序只需数排序只需4 4次。次。桶排序（过程及分析）桶排序（过程及分析）n桶排序思想桶排序思想n桶排序算法桶排序算法n桶排序分析桶排序分析 桶排序思想桶排序思想n 桶排序的思想就是把区间桶排序的思想就是把区间0,1)0,1)划分划分成成n n个相同大小的子区间个相同大小的子区间,或称桶或称桶,然后将然后将n n个输入数分布到各个桶中去。如果输入个输入数分布到各个桶中去。如果输入数均匀分布在数均匀分布在0,1)0,1)上上,则一般不会有很多则一般不会有很多数落在一个桶中。为得到结果数落在一个桶中。为得到结果,先对各个先对各个桶中的数进行排序桶中的数进行排序,然后按次序把各个桶然后按次序把各个桶中的元素列出来即可。中的元素列出来即可。桶排序算法桶排序算法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,.,Bn-1B0,B1,.,Bn-1按顺序合并按顺序合并桶排序算法桶排序算法桶排序分析桶排序分析n正确性：反证法正确性：反证法n时间代价：时间代价：桶排序分析桶排序分析排序算法稳定性排序算法稳定性n若待排序的序列中，存在多个具有相同若待排序的序列中，存在多个具有相同值的元素，经过排序，这些元素的相对值的元素，经过排序，这些元素的相对次序保持不变，则称该算法是稳定的；次序保持不变，则称该算法是稳定的；若经排序后，元素的相对若经排序后，元素的相对 次序发生了改次序发生了改变，则称该算法是不稳定的。变，则称该算法是不稳定的。常见排序算法的稳定性常见排序算法的稳定性n堆排序算法堆排序算法 不稳定不稳定n快速排序算法快速排序算法 不稳定不稳定n归并排序算法归并排序算法 稳定稳定n直接插入排序算法直接插入排序算法 稳定稳定n冒泡排序算法冒泡排序算法 稳定稳定n计数排序算法计数排序算法 稳定稳定n桶排序算法桶排序算法 稳定稳定程序演示及说明程序演示及说明n(程序演示及说明程序演示及说明)作业作业n思考题思考题9-29-2：以线性时间作原地置换排序：以线性时间作原地置换排序The EndThe EndnThank you!Thank you!
