云大《数据结构》课程教学课件-第10章 内部排序.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 2-路归并排序演示 下面给出一个2-路归并排序的例子 初始关键字 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 * 算法分析 与快速排序和堆排序相比，归并排序的最大特点是，它是一种稳定的排序方法。但在一般情况下，很少用2-路归并排序法进行内部排序。 2-路归并排序的时间复杂度为O(nlogn)。 * 第六节 基数排序 * 基数排序 基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。 定义 假设含有 n 个记录的序列为： 　　　 {R1，R2，….，Rn} 且每个记录 Ri 中含有 d 个关键字，则称该序列对关键字有序指：对于序列中任意两个记录 Ri 和 Rj（1≤ij≤n）都满足下列有序关系 　　　 其中 K0 被称作最主位关键字，Kd-1 被称作最次位关键字 * 基数排序 多关键字排序经常用到的两种方法。 最高位优先法(Most Significant Digit first) 最低位优先法(Least Significant Digit first) * 链式基数排序 链式基数排序类似于表插入排序，附设指针数组将顺序表视作一个“静态链表”，利用“修改指针”实现分配和收集。 同时设置rd个队列的头指针和尾指针，分别指示各队列的头结点和尾结点在链表中的位置。 * 链式基数排序演示 初始态 一趟分配 e[0] e[1] e[2] e[4] e[3] e[6] e[5] e[7] e[9] e[8] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0] 278 109 063 930 589 184 505 269 008 083 269 589 109 930 083 063 184 505 008 278 一趟收集 930 063 083 184 505 278 008 109 589 269 依次按次高位，最高位进行分配收集 * 算法分析 对于n个记录进行链式基数排序的时间复杂度为O(d(n+rd)) 其中每一趟分配的时间复杂度为O(n)， 每一趟收集的时间复杂度为O(rd), 整个排序需要进行d趟分配和收集。 所需空间为2rd个队列指针。当然，由于需用链表作存储结构，则相对于其他以顺序结构存储记录的排序方法而言，还增加了n个指针域的空间。 * 第七节 各种内部排序方法的比较讨论 * 各种排序方法的比较讨论 排序方法 平均时间 最坏情况 辅助存储 稳定性 简单排序 O(n*n) O(n*n) O(1) √ 快速排序 O(nlogn) O(n*n) O(logn) × 堆排序 O(nlogn) O(nlogn) O(1) × 归并排序 O(nlogn) O(nlogn) O(n) √ 基数排序 O(d(n+rd)) O(d(n+rd)) O(rd) √ 各种排序方法的性能分析如下表所示： * 各种排序方法的比较讨论 记录较大的序列采用的方法 对于表插入排序，链式基数排序可采用静态链表作存储结构 对于不能实现表排序的方法，如快速排序，堆排序，可以进行“地址排序”。 * 各种排序方法的比较讨论 例如，对如下序列进行排序 R(49) R(65) R(38) R(27) R(97) R(13) R(76) R(49) r(1 : 8) 1 2 3 4 5 6 7 8 adr[1 : 8] … … 6 4 3 1 8 2 7 5 adr[1 : 8] 令adr[i]：=i 可附设向量adr(1 : 8) 在排序过程中需进行r[i] ：= r[j]的操作时，均以adr[i]： = adr[j]代替 * 各种排序方法的比较讨论 排序结束后，地址向量中的值指示排序后的记录的次 序，r[adr[1]]为关键字最小的记录，r[adr[8]]为关键字最大的记录，最后根据需要重排记录的物理位置 R(13) R(27) R(38) R(49) R(97) R(65) R(76) R(49) r(1 : 8) 1 2 3 4 8 6 7 5 adr[1 : 8] 除了在每个小