第9章 排序（ sorting）数据结构课件.PPT

习题、考题： 1. 9-9 2. 在一个有n个结点的循环单链表（不带表头结点）中，各个结点按data域的值从小到大链接，链表中有两个指针h和r， 其中h始终指向链表中data域最小结点， 指针r指向刚刚被搜索到的结点。 现采用下述搜索方法：设给定的值为k， 首先将k与r所的结点的data域比较, 若 k=r-data, 则自r出发进行搜索， 否则自h出发进行搜索， 直到搜索成功。假定每个结点的搜索概率相等， 试讨论搜索成功的平均搜索长度ASLsucc。 O(n+radix) 4) 算法分析 初始化桶 O（radix） 分配桶 O（n） 收集桶 O（radix） 循环d次，所以，总执行时间为O(d.(n+radix) 附加时间：O(n+2radix) 指针 桶指针 5) 稳定的 第5章 内排序小结 排序方法 比较次数 平均比较次数 稳定性 移动次数 辅助存储 1、插入排序 最小 最大 最小 最大 直接插入排序 O(n2) 稳定 O(1) 2n n2/2 n n2/2 二分法插入排序 O(nlog2n) 稳定 O(1) 2n n2/2 nlog2n 表插入排序 O(n2) 稳定 O(n) 0 0 n n2/2 shell排序 不稳定 O(1) 2、选择排序 直接选择排序 O(n2) 不稳定 O(1) n(n-1)/2 3(n-1) 堆排序 O(nlog2n) 不稳定 O(1) O(nlog2n) Bubble Sort 稳定 0 3、交换排序 3/2·n(n-1) Quick Sort 不稳定 O(log2n) O(1) n-1 O(n2) nlog2n O(nlog2n) n(n-1)/2 n2/2 ? nlog2n 4、分配排序 基数排序 稳定 O(n+r) O(d·(n+r)) O(d·(n+r)) 拉链 5、归并排序 稳定 O(n) O(n·log2n)) O(n·log2n)) 。。。 data link h r 20:n 21:2*(n/2) 22:4*(n/4) …… 2k: 设n=2k,一共做了K趟 K=log2n T(n)?n+2T(n/2)?n+2(n/2+2T(n/4))=2n+22T(n/22) ?2n+22(n/22+2T(n/23))=3n+23T(n/23) ?… ?kn+2kT(n/2k)=nlog2n+nT(1)=O(nlog2n) 可以证明Quicksort的平均计算时间也是O（nlog2n ） 因为一般情况：n个记录被分成两个子序列，分别 含有r和n-r个对象，则比较次数 C（n）=n+C（r）+C（n-r） C（n）不仅依赖于n，而且依赖于表中记录的排列顺序。 下面讨论空间复杂性： 以上讨论的是递归算法，也可用非递归算法来实现。 不管是递归（由编译程序来实现）还是非递归。第一次 分划后，左部、右部要分别处理。 所以，用栈来存放： (1) 存放什么：左部或右部的上、下界的下标。 (2) 放长的还是短的：放长的 (3) 栈要多大：O（log2n）?放短的O（n） 9.4 选择排序 方法：1.直接选择排序 2.锦标赛排序 3.堆排序 1. 直接选择排序 思想：首先在n个记录中选出关键码最小（最大）的记录， 然后与第一个记录（最后第n个记录）交换位置， 再在其余的n-1个记录中选关键码最小（最大）的记 录，然后与第二 个记录（第n-1个记录）交换位置， 直至选择了n－1个记录。 例子: 0 1 2 3 4 5 21 25 49 25* 16 08 08 [25 49 25* 16 21] 08 16 [49 25* 25 21 ] 08 16 21 [25* 25 49 ] 08 16 21 25* 25 49] 08 16 21 25* 25 49 算法： template