一章排序.pptVIP

第3章 排 序 理解递归排序算法Msort 第7次上机作业 1.实现双向链表的插入、删除、输出元素。 2. 实现归并排序。 * * 排序本身涉及的数据结构类型比较单纯，所用的存储结构为顺序表。把排序的内容安排在第 2 章的线性表之后，可巩固第 2 章所学的知识，也有利算法分析能力的提高。 其中有些排序的内容需要树的知识做基础，这些内容被安排在第 6 章来继续学习。例如，堆排序的实现放到 “二叉树的应用”一节；归并排序的跟读需要借助“二叉树遍历”的知识做铺垫等。 讲授本章课程大约需6课时。 3.3 先进排序方法 三、内部排序的方法 　　内部排序的过程是一个逐步扩大 记录的有序序列长度的过程。 经过一趟排序 有序序列区 无 序 序 列 区 有序序列区 无 序 序 列 区 二、归并排序 　归并排序的过程基于下列基本思想进行： 将两个或两个以上的有序子序列 “归并” 为一个有序序列。 　　在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列 归并为一个记录的有序序列。 有 序 序 列 R[l..n] 有序子序列 R[l..m] 有序子序列 R[m+1..n] 这个操作对顺序表而言，是轻而易举的。 void Merge (RcdType SR[], RcdType TR[], int i, int m, int n) { // 将有序的记录序列 SR[i..m] 和 SR[m+1..n] // 归并为有序的记录序列 TR[i..n] } // Merge for (j=m+1, k=i; i=m j=n; ++k) { // 将SR中记录由小到大地并入TR if (SR[i].key=SR[j].key) TR[k] = SR[i++]; else TR[k] = SR[j++]; } … … // 处理某一个表的剩余尾部 if (i=m) TR[k..n] = SR[i..m]; // 将剩余的 SR[i..m] 复制到 TR if (j=n) TR[k..n] = SR[j..n]; // 将剩余的 SR[j..n] 复制到 TR 处理某一个表的剩余尾部代码段: 归并排序的算法 　如果记录无序序列 R[s..t] 的两部分 R[s..?(s+t)/2?] 和 R[?(s+t)/2?+1..t] 已经分别按关键字有序， 则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列。 由此，应该先分别对这两部分进行 2-路归并排序。 例如： 52, 23, 80, 36, 68, 14 (s=1, t=6) [ 52, 23, 80] [36, 68, 14] [ 52, 23][80] [ 52] [ 23, 52] [ 23, 52, 80] [36, 68][14] [36][68] [36, 68] [14, 36, 68] [ 14, 23, 36, 52, 68, 80 ] [23] void Msort ( RcdType SR[], RcdType TR1[], int s, int t ) { // 将SR[s..t] 归并排序为 TR1[s..t] if (s= =t) TR1[s]=SR[s]; else { } } // Msort … … // 归并排序的主要操作 m = (s+t)/2; // 将SR[s..t]平分为SR[s..m]和SR[m+1..t] Msort (SR, TR2, s, m); // 递归地将SR[s..m]归并为有序的TR2[s..m] Msort (SR, TR2, m+1, t); //递归地SR[m+1..t]归并为有序的TR2[m+1..t] Merge (TR2, TR1, s, m, t); // 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] 归并排序主要操作的代码段: void MergeSort (SqList L) { // 对顺序表 L 作2-路归并排序 MSort(L.r, L.r, 1,