线性时间排序培训课件.ppt

《线性时间排序培训课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第8章：线性时间排序2本章内容介绍了几种O(nlgn)的排序算法：合并排序和堆排序达到此上界；快速排序平均情况下达到此上界；比较排序算法的下界线性时间排序：计数排序（CountingSort）基数排序（RadixSort）桶排序（BucketSort）38.1排序算法的下界比较排序算法的作用比较排序算法仅用来确定输入序列的元素间次序，即给定两个元素ai和aj,测试aiaj中哪一个成立。48.1排序算法的下界决策树模型比较排序可以被抽象的视为决策树。一棵决策树是一棵满二叉树，表示

2、某排序算法作用于给定输入所做的所有比较。(6,8,5)5决策树在决策树中，对每个内结点都注明i：j，其中1≤i，j≤n，n是输入序列中的元素个数。对每个叶结点都注明排列(π(1),π(2),…,π(n))。排序算法的执行对应于遍历一条从树的根到叶结点的路径。在每个内节结点处要做比较要使排序算法能正确的工作，其必要条件是，n个元素的n!种排列中的每一种都要作为决策树的一个叶子而出现。aiaj6最坏情况下界在决策树中，从根到任意一个可达叶节点之间最长路径的长度，表示对应的排序算法中最坏情况下的比较次数。这样，一个比较排序算法中的最坏情况比较次数就与其决策树的

3、高度相等。定理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)与定

4、理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]

5、←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

6、[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)时，运

7、行时间为O(n)。计数排序的特点计数排序算法没有用到元素间的比较，它利用元素的实际值来确定它们在输出数组中的位置，不是一个基于比较的排序算法，从而它的计算时间下界不再是Ω(nlogn)由于算法第4行使用了downto语句，经计数排序，输出序列中值相同的元素之间的相对次序与他们在输入序列中的相对次序相同，因此计数排序算法是一个稳定的排序算法。在卫星数据排序和基数排序中间应用。158.3基数排序基数排序(radixsort)是一种用在老式穿卡机上的算法。一张卡片有80列，每列可在12个位置中的任一处穿孔。排序器可被机械地“程序化”以检查每一迭卡片中的某一列，再

8、根据穿孔的位置将它们分放12个盒子里。这样，操作员就可逐个地把它们