第10章_内部排序((新).ppt

第十章 内部排序 存储方式 排序算法的评价 10.2 插入排序 10.3 快速排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 10.7 各种内部排序 方法的比较讨论 49 38 65 97 76 13 27 [ ][ ][ ][ ][ ][ ][ ] [38 49] [65 97] [13 76] [27] [38 49 65 97] [13 27 76] [13 27 38 49 65 76 97] 初始关键字 第一趟归并 第二趟归并 第三趟归并 若 2i-1＜n≤2i，所需趟数为 i = ?log2n? 归并排序性能分析： 　容易看出，对 n 个记录进行归并排序的时间复杂度为Ο(n·log2n)。即： 每一趟归并的时间复杂度为 O(n)， 总共需进行 ?log2n? 趟。 归并排序性能分析： 　归并排序需要附加一倍的存储量，归并排序是辅助存储量最多的一种排序方法。 10.6.1 多关键字的排序 设有n 个记录的序列 ( R1, R2, …, Rn )，其中每个记录Ri 含有d 个关键字( Ki1, Ki2,…, Kid ) ， 其中: K1 被称为 最主位（最高位）关键字， Kd 被称为 最次位（最低位）关键字。 若对于序列中任意两个记录Ri 和Rj (1?ij?n) 都满足下列（词典）有序关系： ( Ki1, Ki2,…,Kid )＜( Kj1, Kj2,…,Kjd ) 则称记录序列 ( R1, R2, …,Rn ) 对关键字( K1, K2,…,Kd ) 有序。 实现多关键字排序通常有两种方法: 最高位优先法(MSD法)和最低位优先法(LSD法) 先对K1进行排序，并按K1 的不同值将记录序列分成若干子序列之后，分别对K2 进行排序， ...…，依次类推，直至最后对最低位关键字排序完成为止。 最高位优先(Most Significant Digit first)法 先对Kd进行排序，然后对Kd-1进行排序,……，依次类推，直至对最高位关键字 K1 排序完成为止。 最低位优先(Least Significant Digit first)法 MSD和LSD只约定按什么样的关键字次序来进行排序，并未规定对每个关键字进行排序时所用的方法。 在LSD法的排序过程中，不需要根据上一个关键字的排序结果将记录序列分割成若干个（上一个关键字不同的）子序列，对每个关键字都是整个序列参加排序。但对Ki(1?id)进行排序时，只能用稳定的排序方法。 在按LSD排序时，也可以不利用前几节讨论的各种排序方法，而是通过若干次“分配”和“收集”实现排序，这样做不需要进行关键字的比较。 * 通过“分配-收集”实现排序的方法称作分配排序。 10.6.2 链式基数排序 　对于数字型或字符型的单逻辑关键字，可以看成是由多个数位或多个字符构成的多关键字,此时可以按 LSD 法通过“分配-收集”进行排序: 从最低位关键字起，按关键字的不同值依次将序列中记录分配到 rd 个队列中，然后收集之,如此重复 d 次，便可完成排序。 rd —— 基数（各位关键字的可能取值个数） d —— 关键字位数 　基数排序是一种借助多关键字排序的思想来实现单逻辑关键字排序的内部排序方法。 　在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体做法为： 待排序记录以指针相链，构成一个链表； “分配”时，按当前关键字位所取值，将记录分配到相应的链队列中，每个队列中记录的 当前关键字位取值相同； “收集”时，按当前关键字位取值从小到大依次将各队列首尾相链，成为一个链表; 对每个关键字位均重复 2) 和 3) 两步。 例： p→369→367→167→239→237→138→230→139 第一次分配 第一次收集 f[0] r[0] f[7] r[7] f[8] r[8] f[9] r[9] p→230 →230← →367 ← →167 →237 →367→167→237 →138 →368→239→139 →369 ← →239 →139 →138← 按个位有序 第二次分配 p→230→237→138→239→139 p→230→367→