《{时间管理}第8章线性时间排序算法分析与设计杭电褚一平》由会员分享，可在线阅读，更多相关《{时间管理}第8章线性时间排序算法分析与设计杭电褚一平（28页珍藏版）》请在金锄头文库上搜索。
1、第8章：线性时间排序,2,本章内容,介绍了几种O(nlgn)的排序算法：,合并排序和堆排序达到此上界； 快速排序平均情况下达到此上界；,比较排序算法的下界 线性时间排序：,计数排序（Counting Sort） 基数排序（Radix Sort） 桶排序（Bucket Sort）,3,8.1 排序算法的下界,比较排序算法的作用,比较排序算法仅用来确定输入序列a1,a2, . . ., an的元素间次序，即给定两个元素ai 和aj, 测试ai aj 中哪一个成立。,4,8.1 排序算法的下界,决策树模型,比较排序可以被抽象的视为决策树。一棵 决策树是一棵满二叉树，表示某排序算法 作用于给定输入所做
2、的所有比较。(6,8,5),5,决策树,在决策树中，对每个内结点都注明i：j，其中 1i，jn，n是输入序列中的元素个数。 对每个叶结点都注明排列 (1),(2),(n)。,排序算法的执行对应于遍历一条从树的根到叶 结点的路径。在每个内节结点处要做比较,要使排序算法能正确的工作，其必要条件是，n 个元素的n!种排列中的每一种都要作为决策树 的一个叶子而出现。,ai a j,6,最坏情况下界,在决策树中，从根到任意一个可达叶节点之间 最长路径的长度，表示对应的排序算法中最坏 情况下的比较次数。这样，一个比较排序算法 中的最坏情况比较次数就与其决策树的高度相 等。,定理8.1 任意一个比较排序算法
3、在最坏情况 下，都需要(nlgn)次的比较。,于2 ，则有,n!l 2,定理8.1的证明 证明：对于一棵每个排列都作为一个可达叶结点出现的 决策树，根据前面的讨论即可确定其高度。考虑一棵高 度为h的、具有l个可达叶结点的决策树，它对应于对n 个元素所做的比较排序。因为n个输入元素共有n!种排 列，每一种都作为一个叶子出现在树中，故有n!l。 又由于在一棵高为h的二叉树中，叶子的数目不多,对该式取对数，得到 hlg(n!)=(nlgn) 推论8.2堆排序和归并排序是渐进最优的比较算法 证明：堆排序和归并排序的运行时间上界O(nlgn)与定理 8.1给出的最坏情况下界 (nlgn)一致 7,h,h
4、,8,8.2 计数排序,计数排序假设n个输入元素中的每一个都是介于 0到k之间的整数，此处k为某个整数，当k=O(n) 时，技术排序的运行时间是O(n)。,计数排序的基本思想就是对每一个输入元素x， 确定出小于x的元素个数。有了这一信息，就可 以 把x直接放到它在最终输出数组中的位置上。 在计数排序算法中，我们假设输入时隔数组 A1.n，length(A)=n。另外还需要两个数组： 存放排序结果的B1.n，以及提供临时存数区 的C1.k,9,计数排序程序,COUNT-SORT(A,B,k),1 for i0 to k 2 do Ci0,3 for j1 to lengthA,4 do CAj
5、CAj + 1,5 Ci 现在包含等于i的元素个数 6for i 1 to k,7 do Ci Ci + Ci - 1,8 Ci现在包含小于或等于i的元素个数 7 for j lengthA downto 1 8 do BCAj Aj,9 CAj CAj - 1,10,计数排序过程,1,2,11,计数排序过程,3,4,12,计数排序过程,5,6,算法说明,在第9-11行中的for循环部分，把每个元素 Aj放在输出数组B中与其相应的最终位置 上。如果所有n个元素都不相同，则当第 一次执行到第9行时，对每个Aj，值,CAj即为Aj在输出数组中的最终正确位 置，因为共有CAj个元素小于等于Aj。 由
6、于各个元素可能不一定是不同的，因 此，每当将一个值Aj放入数组B中时，都 要减少CAj的值。这会使得下一个其值 等于Aj的输入元素（如果存在的话）直 接进入数组B中Aj的前一个位置上,14,计数排序时间代价,计数排序时间代价,算法第12行的for循环所花时间为(k)。第34行中for循环所 花时间为(n)，第67行for循环所花时间为(k)，第911行 的for循环所花时间为(n)。这样，总的时间就是(k+n)。实 践中，当k=O(n)时，运行时间为O(n)。 计数排序的特点,计数排序算法没有用到元素间的比较，它利用元素的实际 值来确定它们在输出数组中的位置，不是一个基于比较的 排序算法，从而
7、它的计算时间下界不再是(nlogn),由于算法第4行使用了downto语句，经计数排序，输出序列 中值相同的元素之间的相对次序与他们在输入序列中的相 对次序相同，因此计数排序算法是一个稳定的排序算法。 在卫星数据排序和基数排序中间应用。,15,8.3 基数排序,基数排序(radix sort)是一种用在老式穿卡机上的算法。,一张卡片有80列，每列可在12个位置中的任一处穿孔。排序器可被机 械地“程序化”以检查每一迭卡片中的某一列，再根据穿孔的位置将它 们分放12个盒子里。这样，操作员就可逐个地把它们收集起来。其中 第一个位置穿孔的放在最上面，第二个位置穿孔的其次，等等。 对 十进制数字来说，每
8、列中只用到10个位置(另两个位置用于编码非数 值字符)。一个d位数占用d个列。因为卡片排序器一次只能查看一个 列，要对n张片上的d位数进行排序就要有个排序算法。,直觉上，大家可能觉得应该按最重要的一位排序，然后对 每个盒子中的数递归地排序，最后把结果合并起来。与人 们的直觉相反，基数排序是首先按最低有效位数字进行排 序，以解决卡片排序问题。 RADIX-SORT(A,d),1 for i 1 to d,do use a stable sort to sort array A on digit i,16,8.3 基数排序例子,17,基数排序定理,引理8.3 给定n个d位数，每一个数可以取k中可
9、能的值。如果所用的稳定排序需要(n+k)的时 间，基数排序算法能以(d(n+k)的时间正确的 对这些数进行排序,证明：基数排序的正确性可以通过对正在被排 序的列进行归纳而加以证明。对本算法时间代 价的分析要取决于选择哪一种稳定的中间排序 算法。当每位数字都界于0到k-1之间，且k不太 大时，可以选择计数排序。对n个d位数的每一 遍处理的时间为(n+k)，共有d遍，故基数排 序的总时间为(d(n+k),时间内正确的对这 2/b r n ,RADIX-SORT能在, 2n ,序的每一遍需要时间为(n+k)= ，共有,18,基数排序定理,引理8.4 给定n个b位数和任何正整数rb，,些数进行排序。,
10、例如：可以将一个32位的字视为有4个8位的数 字，于是有b=32, r=8, k=2r-1=r8-1=255,d=b/r=4.,r,证明：对于以一个值rb，将每个关键字看做 是有 d b / r 个数字，每个数字都包含r位。每 一个数字都是介于0到 2r 1之间的一个整数，这 样就可以采用基数排序，此处k= 2 r 1。计数排,r,d遍，总的运行时间为 b / r n 2r ,定理说明,对于给定的n值和b值，我们希望所选择的r值（rb） 能够最小化表达式(b/r)(n+2r),(n)。于是，选择r=b得到的运行时间为(b/b)(n+rb)= (n),从渐进意义上来看，这一时间是最优的。,子内的
11、最佳时间，如此选择得到的运行时间为,lg n,lg n, ,20,基数排序时间,基数排序是否要比基于比较的排序算法更好？ 如果根据常见的情况有b=O(lgn)并选择rlgn，则基 数排序的运行时间为O(n)，这看上去要比快速排序 的平均情况时间O(nlgn)更好些。,在这两个时间中隐含在O记号中的常数因子是不同 的。对于要处理的n个关键字，尽管基数排序执行的 遍数可能要比快速排序要少，但每一遍所需的时间 都要长得多。,此外，利用计数排序作为中间稳定排序的基数排序 不是原地排序，而很多O(nlgn)时间的比较排序算法 则可以做到原地排序。因此当内存容量比较宝贵 时，像快速排序这样的原地排序算法可
12、能是更为可 取的。,8.4 桶排序,平均情况下桶排序以线性时间运行,假设输入由一个随机过程产生，该过程将元素一致地分 布在区间0，1)上。,桶排序的思想就是把区间0，1)划分成n个相同大小的 子区间，或称桶。然后，将n个输入数分布到各个桶中 去。因为输入数均匀且独立均匀分布在0，1)上，所 以，一般不会有很多数落在一个桶中的情况。为得到结 果，先对各个桶中的数进行排序，然后按次序把各个桶 中的元素列出来即可。,22,8.4 桶排序,在桶排序算法的代码中，假设输入是个含n个元素的数 组A，且每个元素满足0 Ai1。另外还需要一个辅助 数组B0.n-1来存放链表实现的桶，并假设可以用某种 机制来维
13、护这些表。,BUCKET-SORT(A),1 nlengthA 2 for i 1 to n,4 for i 0 to n-1,5 do sort list Bi with insertion sort,6 concatenate the lists B0，B1，Bn-1together in order,3 do insert Ai into list B nAi ,23,桶排序过程,下图演示了桶排序作用于有10个数的输入数组上的操作过程。(a) 输入数组A1.10。(b)在该算法的第5行后的有序表(桶)数组 B0.9。桶i中存放了区间i/10，(i+1)/10上的值。排序输出由表 BO、B
14、1、.、B9的按序并置构成。,24,桶排序算法的正确性,给任意两个元素Ai和Aj，不失一般性， 假设AiAj。由于floor(nAi),floor(nAj)。，元素Ai或者被放入Aj 所在桶中，或者被放入一个下表更小的桶 中。如果Ai和Aj落入同一个桶中，则第 4-5行中的for循环会将它们按适当的顺序 排列。如果Ai和Aj落入了不同的桶中， 则第6行将它们按适当的顺序排列，因 此，桶排序是能正确工作的。, (n) E O(ni2 ), (n) O E (ni2 ),25, ,n 1 i 0 n 1 i 0,桶排序算法的运行时间 除第5行外，所有各行在最坏情况的时间都是O(n)。唯 一需要分析
15、的部分就在于第5行中插入排序所花的时 间。 为分析调用插入排序的时间代价，设n_i为表示桶Bi中 元素个数的随机变量。因为插入排序以二次时间运行， 因而桶排序的运行时间： n 1 T (n) (n) O(ni2 ) i 0 对上式两边取期望，并利用期望的线性性质， n 1 i 0 ,桶排序算法的运行时间,下式,i,En 2 2 1 / n,对i=0，1，n-1是成立的。每一个桶i有相同 的值 Eni2 是不足为奇的，因为输入数组A中的每 一个值都是等可能地落在任何桶内的。为了证 明上式，我们定义指示器随机变量 X ij I A j落在桶i中 其中，i=0,1,n-1, j=1,2,n。于是，
16、n j 1 项进行重新组合： 26, EX, E X ij2 ,E X ij2 1* 0* ,1 , ,1 1,E n , ,j 1 1 j n 1 k n n,n, n(n 1) * 2 1 , 2 ,27, ,k j,ij,X ik,n j 1 1 j n 1 k n,桶排序算法的运行时间 2 X X j 1 j 1 k 1 k j ,(8.3),X ij 为,我们分别计算两个和式。指示器随机变量 1的概率为1/n，其他情况下为0.于是有 1 1 1 n n n 将这两个期望值替换进式8.3，有,n,k j,i 2,2,n 1 1 n n,1 n,1 n, n *,28,桶排序算法的运行时间,因此，桶排序的期望运行时间为(n) + n*O(2-,1/n)= (n),
