第十章内部排序.ppt

时间和空间 算法运算时需要两种资源：时间资源与空间资源。需要时间资源的量叫时间复杂度，需要空间资源的量叫空间复杂度。 算法的时间复杂度与空间复杂度是一个问题的两个方面，也是一对矛盾，它们之间一般存在着此消彼长的关系。 时间和空间 若降低空间复杂度，往往会增大时间复杂度 （比如：局部修路往往造成堵塞） 若增加空间复杂度，往往可以减小时间复杂度 （比如：城市高架，大楼增加消防逃生通道） 但空间复杂度增长到一定程度，时间复杂度往往不再减小 时间 空间 例子 适当增加空间资源，减小算法的时间复杂度 a) 顺序查找，若增加一个“哨兵”变量，可略去下标下越界检查，比较次数大约减小一半； b) 单循环链表比单链表仅仅增加了一个指向头结点的指针，但其最大好处在于能从任一结点位置访问其他结点； c) Hash表的平均查找长度与装填因子呈正相关关系，若适当增加Hash表长度，减小装填因子，则可减小查找的时间复杂度。 时间和空间 若降低时间复杂度，往往需要增大空间复杂度 （比如：解决堵车问题） 若增加时间复杂度，往往可以减小空间复杂度 （以时间换空间，例如：十字路口的红绿灯） 时间和空间 对算法来说，时间资源和空间资源相比较而言 时间资源更为宝贵！ 三、排序方法的稳定性能 1. 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。 排序之前 : { · · · · · Ri(K) · · · · · Rj(K) · · · · · } 排序之后 : { · · · · · Ri(K) Rj(K) · · · · ·· · · · · } 例如： 排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 ) 若排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 ) 则称该排序方法是稳定的; 若排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 ) 则称该排序方法是不稳定的。 2. 对于不稳定的排序方法，只要能举出一个实例说明即可。 4. 快速排序、堆排序和希尔排序是不稳定的排序方法。 例如 : 对 { 4, 3, 4, 2 } 进行快速排序， 得到 { 2, 3, 4, 4 } 四、关于“排序方法的时间复杂度的下限” 前面讨论的各种排序方法都是基于“比较关键字”进行排序的排序方法。 可以证明， 这类排序法可能达到的最快的时间复杂度为O(nlogn)。 三个元素比较的判定树 最少比较2次，对应第3层的叶子 最多比较3次，对应第4层的叶子 K1K2 K1K3 K2K3 K3K2K1 K2K3 K1K3 K1K2K3 K2K1K3 K2K3K1 K3K1K2 K1K3K2 思考：n个元素排序 （最好情况）至少需要几次比较？ 若K1K2, K2K3,…,Kn-1Kn, 则需n-1次比较 （最坏情况）至少需要几次比较？ 难道必须两两比较，构建一个无向完全图？ (n-1)+(n-2)+…+1 = n(n-1)/2 存在冗余操作！没必要！由于传递性，若K1K2, K2K3,则无需进行K1和K3的比较！ n个元素排序 可能出现的初始序列有n!个 对应于判定树上的n!个叶子结点 若少一个叶子，说明还有两种状态还没有分辨出来 若二叉树高为h，则叶子结点个数n0≤2h-1 即：h≥logn0+1, h为整数，则有h ≥ 反之，若有u个叶子，则二叉树高度 ≥ 今有n!个叶子，则判定树上必存在一个层数为 的叶子结点（对应于比较 次） 小结 任何一个借助于关键字“比较”进行排序的算法，在最坏情况下，所需进行的比较次数至少为 结论：借助于“比较”进行排序的算法，在最坏情况下，能达到的最好的时间复杂度为O(nlogn)! 南京理工大学 祝你成功！ 南京理工大学 世界是你们的！ 1. 了解排序的定义和各种排序方法的特点。熟悉各种方法的排序过程及其依据的原则。基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类。 本章小结 2. 掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的最好情况和最坏情况的时间性能。 3．理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。 广 告 《算法设计与分析》 II-教