第九章 排序3课件.pptVIP

排序上机习题 1．? 奇偶交换排序是另一种交换排序。算法的基本思想如下：排序过程通过对文件x[i]（l≤i≤n）的若干次扫描来完成，第奇数次扫描，对所有下标为奇数的记录x[i]与其后面的记录x[i+1]（l≤i≤n–1）相比较，若x[i].KEY（记录x[i]的关键饲）＞x[i+1].KEY，则交换x[i]和x[i+1]的内容；第偶数次扫描，对所有下标为偶数的记录x[i]与其后面的记录x[i+1]（2≤i≤n–1）相比较，若x[i].KEY＞x[i+1].KEY，则交换x[i]和x[i+1]之内容。一趟奇数次扫描和一趟偶数次扫描被称为一趟奇偶扫描。重复上述过程直到排序完成为止。 （l）排序的终止条件是什么？ （2）完成该算法的具体设计。 （3）当待排序关键字序列的初始排列是从小到大有序，或从大到小有序时，在奇偶交换排序过程中的关键字比较次数是多少？ ; 2、? 有n个记录存储在带头结点的双向链表中，结点结构如图所示。现用双向起泡排序法对其按上升进行排序，请写出这种排序算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡。） ;9.4 合并排序 9.4.1 二路合并排序 1 合并：把两个或多个有序文件组成一个单一的 有序文件。 2 两个文件的合并。 ; 两个有序表R[l] …R[m]和R[m+1] …R[n]。它们可合并成一个有序表，存于另一有序表X[l] …X[n]中。 这种合并方法称为两路合并 (2-way merging)。 其基本思想是：设两个有序表A和B，变量 i 和 j 分别是表A和表B的当前检测指针。设表C是合并后的新有序表，变量 k 是它的当前存放指针。;08 21 25 25* 49 62 72 93 ;此算法的关键码比较次数和对象移动次数均为 (m - t + 1) + (n - m) = n - t + 1。 算法Merge (R，t，m，n. X) ： 假定文件（Rt，Rt＋1，…，Rm）和文件（Rm＋1，…，Rn）都已经排序，该算法合并这两个文件后得到排序好的大文件（Xt，Xt＋1，…，Xn）； 算法Merge()演示;两个有序文件合并成一个大的有序文件 算法Merge (R，t，m，n . X)算法Merge()演示 M1 [初始化给每个文件一个头指针] i←t ．j←m＋l ．k←1 ． M2 [比较 i和 j所指记录] WHILE（i≤m） AND（j≤n） DO （IF Ki≤Kj THEN（Xk←Ri ．i←i＋1） ELSE（Xk←Rj ．j←j＋l）. k←k+1）. M3 [复制余留记录项] WHILE (i≤m) {Xk =Ri ?. i←i＋1. k←k+1.} WHILE (j≤n) {Xk =Rj ?. j←j＋1. k←k+1.} ▌; 3 合并排序。 ;迭代的合并排序算法就是利用两路合并过程进行排序的。其基本思想是： 假设初始对象序列有 n 个对象，第1趟把它看成是 n 个长度为 1 的有序子序列 (归并项)，先做两两合并，得到 ?n / 2? 个长度小于等于 2 的文件 (如果 n 为奇数，则最后一个有序子序列的长度为1)；第2趟长度小于等于 2 的文件，…，如此重复，最后得到一个长度为 n 的有序序列。 第i趟,合并长度小于等于 2i -1的文件 。 若存在2k n = 2k+1, 则需k+1趟合并。 ;算法MPass()调用Merge()函数.;合并排序MSort(R，n) 调用函数Mpass(), ; 算法Merge (R，t，m，n. X) ： 假定文件（Rt，Rt＋1，…，Rm）和文件（Rm＋1，…，Rn）都已经排序，该算法合并这两个文件后得到排序好的大文件（Xt，Xt＋1，…，Xn）； 算法Merge()演示 算法MPass（R，n，1ength．X）：一趟合并算法，该算法执行一趟合并过程，将文件R中长度为length的所有子文件合并到文件X中，n是R的记录个数，该函数调用Merge()函数； 算法MPass()演示 算法MSort(R，n) ：该函数调用函数Mpass(),直接两路合并排序，X是辅助文件； 合并排序MSort(R，n) 演示;不论对于怎样的输入，算法MSort（R，n）的合并趟数是一样的. 对于基本排序的文件，可以修改算法MSort，使得合并的趟数达到最少，具体做法是，对输入记录表进行扫描，导出其中由有序记录组成的若干个子表. 然后基