第8章_线性时间排序_算法分析与设计_杭电_褚一平

第8章：线性时间排序2本章内容介绍了几种O(nlgn)的排序算法：合并排序和堆排序达到此上界；快速排序平均情况下达到此上界；比较排序算法的下界线性时间排序：计数排序（CountingSort）基数排序（RadixSort）桶排序（BucketSort）38.1排序算法的下界比较排序算法的作用比较排序算法仅用来确定输入序列a1,a2,...,an的元素间次序，即给定两个元素ai和aj,测试aiaj,ai≤aj,ai=aj,ai≥aj,或aiaj中哪一个成立。48.1排序算法的下界决策树模型比较排序可以被抽象的视为决策树。一棵决策树是一棵满二叉树，表示某排序算法作用于给定输入所做的所有比较。(6,8,5)5决策树在决策树中，对每个内结点都注明i：j，其中1≤i，j≤n，n是输入序列中的元素个数。对每个叶结点都注明排列(π(1),π(2),…,π(n))。排序算法的执行对应于遍历一条从树的根到叶结点的路径。在每个内节结点处要做比较要使排序算法能正确的工作，其必要条件是，n个元素的n!种排列中的每一种都要作为决策树的一个叶子而出现。aiaj6最坏情况下界在决策树中，从根到任意一个可达叶节点之间最长路径的长度，表示对应的排序算法中最坏情况下的比较次数。这样，一个比较排序算法中的最坏情况比较次数就与其决策树的高度相等。定理8.1任意一个比较排序算法在最坏情况下，都需要Ω(nlgn)次的比较。于2，则有n!≤l≤2定理8.1的证明证明：对于一棵每个排列都作为一个可达叶结点出现的决策树，根据前面的讨论即可确定其高度。考虑一棵高度为h的、具有l个可达叶结点的决策树，它对应于对n个元素所做的比较排序。因为n个输入元素共有n!种排列，每一种都作为一个叶子出现在树中，故有n!≤l。又由于在一棵高为h的二叉树中，叶子的数目不多对该式取对数，得到h≥lg(n!)=Ω(nlgn)推论8.2堆排序和归并排序是渐进最优的比较算法证明：堆排序和归并排序的运行时间上界O(nlgn)与定理8.1给出的最坏情况下界Ω(nlgn)一致7hh88.2计数排序计数排序假设n个输入元素中的每一个都是介于0到k之间的整数，此处k为某个整数，当k=O(n)时，技术排序的运行时间是O(n)。计数排序的基本思想就是对每一个输入元素x，确定出小于x的元素个数。有了这一信息，就可以把x直接放到它在最终输出数组中的位置上。在计数排序算法中，我们假设输入时隔数组A[1..n]，length(A)=n。另外还需要两个数组：存放排序结果的B[1..n]，以及提供临时存数区的C[1..k]9计数排序程序COUNT-SORT(A,B,k)1fori←0tok2doC[i]←03forj←1tolength[A]4doC[A[j]]←C[A[j]]+15▹C[i]现在包含等于i的元素个数6fori←1tok7doC[i]←C[i]+C[i-1]8▹C[i]现在包含小于或等于i的元素个数7forj←length[A]downto18doB[C[A[j]]]←A[j]9C[A[j]]←C[A[j]]-110计数排序过程1211计数排序过程3412计数排序过程56算法说明在第9-11行中的for循环部分，把每个元素A[j]放在输出数组B中与其相应的最终位置上。如果所有n个元素都不相同，则当第一次执行到第9行时，对每个A[j]，值C[A[j]]即为A[j]在输出数组中的最终正确位置，因为共有C[A[j]]个元素小于等于A[j]。由于各个元素可能不一定是不同的，因此，每当将一个值A[j]放入数组B中时，都要减少C[A[j]]的值。这会使得下一个其值等于A[j]的输入元素（如果存在的话）直接进入数组B中A[j]的前一个位置上14计数排序时间代价计数排序时间代价算法第1~2行的for循环所花时间为Θ(k)。第3~4行中for循环所花时间为Θ(n)，第6~7行for循环所花时间为Θ(k)，第9~11行的for循环所花时间为Θ(n)。这样，总的时间就是Θ(k+n)。实践中，当k=O(n)时，运行时间为O(n)。计数排序的特点计数排序算法没有用到元素间的比较，它利用元素的实际值来确定它们在输出数组中的位置，不是一个基于比较的排序算法，从而它的计算时间下界不再是Ω(nlogn)由于算法第4行使用了downto语句，经计数排序，输出序列中值相同的元素之间的相对次序与他们在输入序列中的相对次序相同，因此计数排序算法是一个稳定的排序算法。在卫星数据排序和基数排序中间应用。158.3基数排序基数排序(radixsort)是一种用在老式穿卡机上的算法。一张卡片有80列，每列可在12个位置中的任一处穿孔。排序器可被机械地“程序化”以检查每一迭卡片中的某一列，再根据穿孔的位置将它们分放12个盒子里。这样，操作员就可逐个地把它们收集起来。其中第一个位置穿孔的放在最上面，第二个位置穿孔的其次，等等。对十进制数字来说，每列中只用到10个位置(另两个位置用于编码非数值字符)。一个d位数占用d个列。因为卡片排序器一次只能查看一个列，要对n张片上的d位数进行排序就要有个排序算法。直觉上，大家可能觉得应该按最重要的一位排序，然后对每个盒子中的数递归地排序，最后把结果合并起来。与人们的直觉相反，基数排序是首先按最低有效位数字进行排序，以解决卡片排序问题。RADIX-SORT(A,d)1fori←1toddouseastablesorttosortarrayAondigiti168.3基数排序例子17基数排序定理引理8.3给定n个d位数，每一个数可以取k中可能的值。如果所用的稳定排序需要Θ(n+k)的时间，基数排序算法能以Θ(d(n+k))的时间正确的对这些数进行排序证明：基数排序的正确性可以通过对正在被排序的列进行归纳而加以证明。对本算法时间代价的分析要取决于选择哪一种稳定的中间排序算法。当每位数字都界于0到k-1之间，且k不太大时，可以选择计数排序。对n个d位数的每一遍处理的时间为Θ(n+k)，共有d遍，故基数排序的总时间为Θ(d(n+k))时间内正确的对这2/brnRADIX-SORT能在2n序的每一遍需要时间为Θ(n+k)=Θ，共有18基数排序定理引理8.4给定n个b位数和任何正整数r≤b，些数进行排序。例如：可以将一个32位的字视为有4个8位的数字，于是有b=32,r=8,k=2^r-1=r^8-1=255,d=b/r=4.r证明：对于以一个值r≤b，将每个关键字看做是有db/r个数字，每个数字都包含r位。每一个数字都是介于0到2r1之间的一个整数，这样就可以采用基数排序，此处k=2r1。计数排rd遍，总的运行时间为b/rn2r定理说明对于给定的n值和b值，我们希望所选择的r值（r≤b）能够最小化表达式(b/r)(n+2^r)Θ(n)。于是，选择r=b得到的运行时间为(b/b)(n+r^b)=Θ(n),从渐进意义上来看，这一时间是最优的。子内的最佳时间，如此选择得到的运行时间为lgnlgn20基数排序时间基数排序是否要比基于比较的排序算法更好？如果根据常见的情况有b=O(lgn)并选择r≈lgn，则基数排序的运行时间为O(n)，这看上去要比快速排序的平均情况时间O(nlgn)更好些。在这两个时间中隐含在O记号中的常数因子是不同的。对于要处理的n个关键字，尽管基数排序执行的遍数可能要比快速排序要少，但每一遍所需的时间都要长得多。此外，利用计数排序作为中间稳定排序的基数排序不是原地排序，而很多O(nlgn)时间的比较排序算法则可以做到原地排序。因此当内存容量比较宝贵时，像快速排序这样的原地排序算法可能是更为可取的。8.4桶排序平均情况下桶排序以线性时间运行假设输入由一个随机过程产生，该过程将元素一致地分布在区间[0，1)上。桶排序的思想就是把区间[0，1)划分成n个相同大小的子区间，或称桶。然后，将n个输入数分布到各个桶中去。因为输入数均匀且独立均匀分布在[0，1)上，所以，一般不会有很多数落在一个桶中的情况。为得到结果，先对各个桶中的数进行排序，然后按次序把各个桶中的元素列出来即可。228.4桶排序在桶排序算法的代码中，假设输入是个含n个元素的数组A，且每个元素满足0≤A[i]1。另外还需要一个辅助数组B[0..n-1]来存放链表实现的桶，并假设可以用某种机制来维护这些表。BUCKET-SORT(A)1n←length[A]2fori←1ton4fori←0ton-15dosortlistB[i]withinsertionsort6concatenatethelistsB[0]，B[1]，…，B[n-1]togetherinorder3doinsertA[i]intolistB[nA[i]]23桶排序过程下图演示了桶排序作用于有10个数的输入数组上的操作过程。(a)输入数组A[1..10]。(b)在该算法的第5行后的有序表(桶)数组B[0..9]。桶i中存放了区间[i/10，(i+1)/10]上的值。排序输出由表B[O]、B[1]、...、B[9]的按序并置构成。24桶排序算法的正确性给任意两个元素A[i]和A[j]，不失一般性，假设A[i]≤A[j]。由于floor(nA[i])≤floor(nA[j])。，元素A[i]或者被放入A[j]所在桶中，或者被放入一个下表更小的桶中。如果A[i]和A[j]落入同一个桶中，则第4-5行中的for循环会将它们按适当的顺序排列。如果A[i]和A[j]落入了不同的桶中，则第6行将它们按适当的顺序排列，因此，桶排序是能正确工作的。(n)EO(ni2)(n)OE(ni2)25n1i0n1i0桶排序算法的运行时间除第5行外，所有各行在最坏情况的时间都是O(n)。唯一需要分析的部分就在于第5行中插入排序所花的时间。为分析调用插入排序的时间代价，设n_i为表示桶B[i]中元素个数的随机变量。因为插入排序以二次时间运行，因而桶排序的运行时间：n1T(n)(n)O(ni2)i0对上式两边取期望，并利用期望的线性性质，n1i0桶排序算法的运行时间下式iEn221/n对i=0，1，…，n-1是成立的。每一个桶i有相同的值Eni2是不足为奇的，因为输入数组A中的每一个值都是等可能地落在任何桶内的。为了证明上式，我们定义指示器随机变量XijI{A[j]落在桶i中}其中，i=0,1,…,n-1,j=1,2,…,n。于是，nj1项进行重新组合：26EXEXij2EXij21*0*111Enj11jn1knnnn(n1)*21227kjijXiknj11jn1kn桶排序算法的运行时间2XXj1j1k1kj(8.3)Xij为我们分别计算两个和式。指示器随机变量1的概率为1/n，其他情况下为0.于是有111nnn将这两个期望值替换进式8.3，有nkji22n11nn1n1nn*28桶排序算法的运行时间因此，桶排序的期望运行时间为Θ(n)+n*O(2-1/n)=Θ(n)