《第7章排序算法案例》由会员分享，可在线阅读，更多相关《第7章排序算法案例（79页珍藏版）》请在金锄头文库上搜索。
1、1第七章：第七章：排序算法排序算法2排序的概念排序的概念排序是计算机内经常进行的一种操作，其排序是计算机内经常进行的一种操作，其目的是将一组目的是将一组“无序无序”的记录序列调整为的记录序列调整为“有序有序”的记录序列。的记录序列。例如：将下列关键字序列例如：将下列关键字序列52, 49, 80, 36, 14, 58, 61, 23, 97, 75调整为调整为14, 23, 36, 49, 52, 58, 61 ,75, 80, 973假设含假设含n个记录的序列为个记录的序列为 R1, R2, ， Rn 其相应的关键字序列为其相应的关键字序列为 K1, K2, ，Kn 这些关键字相互之间可以
2、进行比较，即在这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系它们之间存在着这样一个关系 ： Kp1Kp2Kpn按此固有关系将上式记录序列重新排列为按此固有关系将上式记录序列重新排列为 Rp1, Rp2, ，Rpn 的操作称作排序。的操作称作排序。排序的概念排序的概念4内部排序和外部排序内部排序和外部排序若若整个排序过程不需要访问外存整个排序过程不需要访问外存便能便能完成，则称此类排序问题完成，则称此类排序问题为内部排序；为内部排序； 反之，若参加排序的记录数量很大，反之，若参加排序的记录数量很大， 整个序列的排序过程整个序列的排序过程不可能在内存中不可能在内存中 完成完成，则称
3、此类排序问题，则称此类排序问题为外部排序为外部排序。5待排记录的数据类型定义待排记录的数据类型定义#define MAXSIZE 1000 / 待排顺序表最大长度待排顺序表最大长度typedef int KeyType; / 关键字类型为整数类型关键字类型为整数类型typedef struct KeyType key; / 关键字项关键字项 InfoType otherinfo; / 其它数据项其它数据项 RcdType; / 记录类型记录类型typedef struct RcdType rMAXSIZE+1; / r0闲置闲置 int length; / 顺序表长度顺序表长度 SqList;
4、 / 顺序表类型顺序表类型6有序序列R1.i-1Ri无序序列 Ri.n一趟直接插入排序的基本思想一趟直接插入排序的基本思想有序序列R1.i无序序列 Ri+1.n7实现实现“一趟插入排序一趟插入排序”分三步进行分三步进行3将Ri 插入插入(复制)到Rj+1的位置上。2将Rj+1.i-1中的所有记录记录均后移后移 一个位置；1在R1.i-1中查找查找Ri的插入位置， R1.j.key Ri.key Rj+1.i-1.key；8直接插入排序直接插入排序9void InsertionSort ( SqList &L ) / 对顺序表 L 作直接插入排序。 for ( i=2; i=L.length;
5、+i ) if (L.ri.key L.ri-1.key) / InsertSortL.r0 = L.ri; / 复制为监视哨for ( j=i-1; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; / 记录后移L.rj+1 = L.r0; / 插入到正确位置10直接插入排序时间分析直接插入排序时间分析最好的情况（关键字在记录序列中顺序有序）：最好的情况（关键字在记录序列中顺序有序）：“比较比较”的次数：的次数：最坏的情况（关键字在记录序列中逆序有序）：最坏的情况（关键字在记录序列中逆序有序）：“比较比较”的次数：的次数：0“移动移动”的次数：的次数：“移动移动
6、”的次数：的次数：11 因为因为R1.i-1 R1.i-1 是一个按关键字有是一个按关键字有序的有序序列，则可以序的有序序列，则可以利用折半查找实现利用折半查找实现“在在R1.i-1R1.i-1中中查找查找RiRi的的插入位置插入位置”，如此实现的插入排序为，如此实现的插入排序为折半插入折半插入排序。排序。折半插入排序折半插入排序1214 36 49 52 80 58 61 23 97 75ilowhighmmlowlowmhigh14 36 49 52 58 61 80 23 97 75ilowhighmhighmhighmlow例如:再如:插入位置插入位置L.rL.r13void BiIn
7、sertionSort ( SqList &L ) / BInsertSort在在 L.r1.i-1中折半查找插入位置；中折半查找插入位置；for ( i=2; i=high+1; -j ) L.rj+1 = L.rj; / 记录后移L.rhigh+1 = L.r0; / 插入14low = 1; high = i-1;while (low=high) m = (low+high)/2; / 折半if (L.r0.key L.rm.key) high = m-1; / 插入点在低半区else low = m+1; / 插入点在高半区15 希尔排序希尔排序 基本思想：对待排记录序列先作“宏观”调
8、整，再作“微观”调整。 所谓“宏观”调整，指的是，“跳跃式”的插入排序。 具体做法为：16 将记录序列分成若干子序列，分别对每个子序列进将记录序列分成若干子序列，分别对每个子序列进行插入排序。行插入排序。 其中，其中，d d 称为增量，它的值在排序过程中从大到小逐称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为渐缩小，直至最后一趟排序减为 1 1。例如：将例如：将 n 个记录分成个记录分成 d 个子序列：个子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 希尔排序希尔排序17例如：例如：16
9、 25 12 30 47 11 23 36 9 18 31 第一趟希尔排序，设增量第一趟希尔排序，设增量 d=5d=511 23 12 9 18 16 25 36 30 47 31 第二趟希尔排序，设增量第二趟希尔排序，设增量 d=3d=39 18 12 11 23 16 25 31 30 47 36第三趟希尔排序，设增量第三趟希尔排序，设增量 d=1d=1 9 11 12 16 18 23 25 30 31 36 47 18void ShellInsert ( SqList &L, int dk ) for ( i=dk+1; i=n; +i ) if ( L.ri.key0&(L.r0.k
10、eyL.rj.key); j-=dk) L.rj+dk = L.rj; / 记录后移，查找插入位置 L.rj+dk = L.r0; / 插入 / if / ShellInsert19void ShellSort (SqList &L, int dlta, int t) / 增量为dlta的希尔排序 for (k=0; k1) / while / BubbleSorti = n;i = lastExchangeIndex; / 本趟进行过交换的 / 最后一个记录的位置 if (Rj+1.key Rj.key) Swap(Rj, Rj+1); lastExchangeIndex = j; /记下进
11、行交换的记录位置 /iffor (j = 1; j i; j+)lastExchangeIndex = 1;23最好的情况（关键字在记录序列中顺序有序）：最好的情况（关键字在记录序列中顺序有序）： 只需进行一趟起泡只需进行一趟起泡“比较比较”的次数：的次数：最坏的情况（关键字在记录序列中逆序有序）：最坏的情况（关键字在记录序列中逆序有序）： 需进行需进行n-1趟起泡趟起泡“比较比较”的次数：的次数：0“移动移动”的次数：的次数：“移动移动”的次数：的次数：n-1冒泡排序时间分析冒泡排序时间分析24一趟快速排序一趟快速排序目标：目标：找一个记录，以它的关键字作为“枢轴枢轴”，凡其关键字小于枢轴关
12、键字小于枢轴的记录均移动至该记录之前移动至该记录之前，反之，凡关键字大于关键字大于枢轴枢轴的记录均移动至该记录之后移动至该记录之后。致使一趟排序一趟排序之后，记录的无序序列Rs.t将分割成两部分分割成两部分：Rs.i-1和Ri+1.t，且 Rj.key Ri.key Rj.key (sji-1) 枢轴枢轴 (i+1jt)。25stlowhigh设设 Rs=52 为枢轴为枢轴 将 Rhigh.key 和 枢轴的关键字进行比较，要求Rhigh.key 枢轴的关键字 将 Rlow.key 和 枢轴的关键字进行比较，要求Rlow.key 枢轴的关键字high23low80high14low52例如例如
13、R052lowhighhighhighlow26int Partition (RedType& R, int low, int high) pivotkey = Rlow.key; while (lowhigh) while (low=pivotkey) -high; RlowRhigh; while (lowhigh & Rlow.key=pivotkey) +low; RlowRhigh; return low; / 返回枢轴所在位置 / Partition27int Partition (RedType R, int low, int high) / Partition R0 = Rlo
14、w; pivotkey = Rlow.key; / 枢轴 while (lowhigh) while(low=pivotkey) - high; / 从右向左搜索Rlow = Rhigh;while (lowhigh & Rlow.key=pivotkey) + low; / 从左向右搜索Rhigh = Rlow;Rlow = R0; return low;28快速排序快速排序 首先对无序的记录序列进行“一次划分一次划分”，之后分别分别对分割所得两个子序列“递归递归”进行快速进行快速排序排序。无无 序序 的的 记记 录录 序序 列列无序记录子序列无序记录子序列(1)(1)无序子序列无序子序列(
15、2)(2)枢轴枢轴一次划分一次划分分别进行快速排序分别进行快速排序29void QSort (RedType & R, int s, int t ) / 对记录序列Rs.t进行快速排序 if (s t-1) / 长度大于1 / QSortpivotloc = Partition(R, s, t); / 对 Rs.t 进行一次划分一次划分QSort(R, s, pivotloc-1); / 对低子序列递归排序，pivotloc是枢轴位置是枢轴位置QSort(R, pivotloc+1, t); / 对高子序列递归排序30快速排序的时间分析快速排序的时间分析假设假设一次划分所得枢轴位置一次划分所得
16、枢轴位置 i=ki=k，则对，则对n n 个记录进个记录进行快排所需时间：行快排所需时间：其中其中 T Tpasspass( (n n) )为对为对 n n 个记录进行一次划分所需时间。个记录进行一次划分所需时间。 若待排序列中记录的关键字是随机分布的，则若待排序列中记录的关键字是随机分布的，则 k k 取取 1 1 至至 n n 中任意一值的可能性相同。中任意一值的可能性相同。T(n) = Tpass(n) + T(k-1) + T(n-k)31设 Tavg(1)b则可得结果：结论结论: 快速排序的时间复杂度为快速排序的时间复杂度为O(nlogn)由此可得快速排序所需时间的平均值为：32 若
17、待排记录的初始状态为按关键字有序若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。快速排序的时间分析快速排序的时间分析33简单选择排序简单选择排序假设排序过程中，待排记录序列的状态为：有序序列R1.i-1无序序列 Ri.n 第 i 趟简单选择排序从中选出关键字最小的记录有序序列R1.i无序序列 Ri+1.n34简单选择排序简单选择排序35void SelectSort (Elem R, int n ) / 对记录序列R1.n作简单选择排序。 for (i=1; i0; -i ) HeapAdjust ( H.r, i, H.l
18、ength ); / 建大顶堆for ( i=H.length; i1; -i ) H.r1H.ri; / 将堆顶记录和当前未经排序子序列 / H.r1.i中最后一个记录相互交换 HeapAdjust(H.r, 1, i-1); / 对 H.r1 进行筛选4098814973556412362740例如例如:是最大堆是最大堆12但在 98 和 12 进行互换之后，它就不不是堆了，因此，需要对它进行“筛选”。98128173641298比较比较比较41void HeapAdjust (RcdType &R, int s, int m) / 已知 Rs.m中记录的关键字除 Rs 之外均 / 满足堆
19、的特征，本函数自上而下调整 Rs 的 / 关键字，使 Rs.m 也成为一个大顶堆 / HeapAdjustrc = Rs; / 暂存 Rs for ( j=2*s; j= Rj.key ) break; / 再作“根”和“子树根”之间的比较， / 若“=”成立，则说明已找到 rc 的插 / 入位置 s ，不需要继续往下调整Rs = Rj; s = j; / 否则记录上移，尚需继续往下调整if ( jm & Rj.keyRj+1.key ) +j; / 左/右“子树根”之间先进行相互比较 / 令 j 指示关键字较大记录的位置43建堆是一个从下往上进行建堆是一个从下往上进行“筛选筛选”的过程的过程
20、40554973816436122798例如例如: : 排序之前的关键字序列为排序之前的关键字序列为123681734998817355 现在，左现在，左/ /右子树都已经调整为堆，最后只要调右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个整根结点，使整个二叉树是个“堆堆”即可。即可。9849406436122744堆排序的时间复杂度分析堆排序的时间复杂度分析1. 对深度为对深度为 k 的堆，的堆，“筛选筛选”所需进行的关键字所需进行的关键字比较的次数至多为比较的次数至多为2(k-1)；3. 调整调整“堆顶堆顶” n-1 次，总共进行的关键次，总共进行的关键 字比较的次数不超过字比较
21、的次数不超过 2 ( log2(n-1) + log2(n-2) + +log22) 2n( log2n ) 因此，因此，堆排序的时间复杂度为堆排序的时间复杂度为O(O(n nloglogn n) )。2. 对对 n 个关键字，建成深度为个关键字，建成深度为h(= log2n +1)的堆，的堆，所需进行的关键字比较的次数至多所需进行的关键字比较的次数至多 4n；45 通常采用的是通常采用的是2-2-路归并路归并排序。即：排序。即：将两个将两个位置相邻的记录有序子序列位置相邻的记录有序子序列归并为一个记录的有序序列。归并为一个记录的有序序列。有有 序序 序序 列列 Rl.n有序子序列有序子序列
22、Rl.m有序子序列有序子序列 Rm+1.n归并排序归并排序46void Merge (RcdType SR, RcdType &TR, int i, int m, int n) / 将有序的记录序列 SRi.m 和 SRm+1.n / 归并为有序的记录序列 TRi.n / Mergefor (j=m+1, k=i; i=m & j=n; +k) / 将将SR中记录由小到大地并入中记录由小到大地并入TR if (SRi.key=SRj.key) TRk = SRi+; else TRk = SRj+; 47if (i=m) TRk.n = SRi.m; / 将剩余的 SRi.m 复制到 TRif
23、 (j=n) TRk.n = SRj.n; / 将剩余的 SRj.n 复制到 TR48归并排序的算法归并排序的算法如果记录无序序列如果记录无序序列 Rs.t 的两部分的两部分 Rs. (s+t)/2 和 R (s+t)/2 +1.t分别按关键字有序，分别按关键字有序， 则利用上述归并算法很容易将它们归则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列。并成整个记录序列是一个有序序列。 由此，应该先分别对这两部分进行由此，应该先分别对这两部分进行 2-路归并排序。路归并排序。49例如：例如：52, 23, 80, 36, 68, 14 (s=1, t=6) 52, 23, 80 36
24、, 68, 14 52, 2380 52 23, 52 23, 52, 8036, 6814366836, 6814, 36, 68 14, 23, 36, 52, 68, 80 2350void Msort ( RcdType SR, RcdType &TR1, int s, int t ) / 将SRs.t 归并排序为 TR1s.t if (s= =t) TR1s=SRs; else / Msort 51m = (s+t)/2; / 将SRs.t平分为SRs.m和SRm+1.tMsort (SR, TR2, s, m); / 递归地将SRs.m归并为有序的TR2s.mMsort (SR,
25、TR2, m+1, t); /递归地SRm+1.t归并为有序的TR2m+1.tMerge (TR2, TR1, s, m, t); / 将TR2s.m和TR2m+1.t归并到TR1s.t52void MergeSort (SqList &L) / 对顺序表 L 作2-路归并排序 MSort(L.r, L.r, 1, L.length); / MergeSort容易看出，对 n 个记录进行归并排序的时间复杂度为(nlogn)。即： 每一趟归并的时间复杂度为 O(n)， 总共需进行 log2n 趟。53非递归的归并排序非递归的归并排序nVoid MergeSort(SqList &list ) l
26、en =1; while( len list.length ) MergePass( list, tempList,len); len *= 2; MergePass( tempList, list, len); len *=2; nVoid MergePass(SqList &initList, SqList &mergedList, int len) int i = 1; while( i+2 * len -1= list.CurrentSize-1 ) merge(initlist, mergedList, i, i+len-1, i+2*len-1 ); i+=2*len; if (
27、i+len= initList. length-1) merge(initlist,mergedList,i,i+len-1,initList. length-1 ); else for (intj = i; j = initList.length-1; j+) mergedList.r j = initLIst.r j ; 54基数排序是一种借助基数排序是一种借助“多关键字排多关键字排序序”的思想来实现的思想来实现“单关键字排序单关键字排序”的内部排序算法。的内部排序算法。基数排序基数排序55多关键字的排序多关键字的排序 n 个记录的序列个记录的序列 R1, R2, ，Rn对关键字对关键字
28、(Ki0, Ki1, ,Kid-1) ) 有序有序是指： 其中其中: : K0 被称为被称为 “最主最主”位关键字位关键字Kd-1 被称为被称为 “最次最次”位关键字位关键字 对于序列中任意两个记录 Ri 和 Rj(1ijn) 都满足满足下列(词典词典)有序有序关系： (Ki0, Ki1, , ,Kid-1) ) (Kj0, Kj1, , ,Kjd-1) )56 先对先对K0进行排序进行排序，并按 K0 的不同值将记录序列分成若干子序列之后，分别对 K1 进行排序，.， 依次类推，直至最后对最次位关键字排序完直至最后对最次位关键字排序完成为止成为止。最高位优先最高位优先MSD法法57 先对 K
29、d-1 进行排序，然后对 Kd-2 进行排序，依次类推，直至对最主位直至对最主位关键字关键字 K0 排序完成为止排序完成为止。最低位优先最低位优先LSD法法58链式基数排序链式基数排序假如多关键字的记录序列中，每个关键字的假如多关键字的记录序列中，每个关键字的取值范围相同，则按取值范围相同，则按LSD法进行排序时，可以法进行排序时，可以采用采用“分配分配- -收集收集”的方法，其好处是不需要进的方法，其好处是不需要进行关键字间的比较。行关键字间的比较。对于数字型或字符型的对于数字型或字符型的单关键字单关键字，可以，可以看看成成是由多个数位或多个字符构成的是由多个数位或多个字符构成的多关键字多关
30、键字，此时可以此时可以采用采用这种这种“分配分配- -收集收集”的办法的办法进行排进行排序序，称作基数排序法称作基数排序法。59链式基数排序链式基数排序601 1、待排序记录以指针相链，构成一个链表；、待排序记录以指针相链，构成一个链表； 2 2、“分配分配” 时，按当前时，按当前“关键字位关键字位”所取值，所取值，将记录分配到不同的将记录分配到不同的 “链队列链队列” 中，每个中，每个队列中记录的队列中记录的 “关键字位关键字位” 相同；相同；3 3、“收集收集”时，按当前关键字位取值从小到时，按当前关键字位取值从小到大将各队列首尾相链成一个链表大将各队列首尾相链成一个链表; ;4 4、对每
31、个关键字位均重复、对每个关键字位均重复 2) 2) 和和 3) 3) 两步。两步。链式基数排序链式基数排序61 基数排序的时间复杂度为基数排序的时间复杂度为O(d(n+rd)其中：分配为其中：分配为O(n) 收集为收集为O(rd)(rd为为“基基”) d为为“分配分配-收集收集”的趟数的趟数堆排序的时间复杂度分析堆排序的时间复杂度分析62各种排序方法时间性能各种排序方法时间性能1.1.平均的时间性能平均的时间性能基数排序基数排序时间复杂度为时间复杂度为 O(O(n nloglogn n) )：快速排序、堆排序和归并排序快速排序、堆排序和归并排序时间复杂度为时间复杂度为 O(n2)O(n2)：直
32、接插入排序、起泡排序和直接插入排序、起泡排序和简单选择排序简单选择排序时间复杂度为时间复杂度为 O(n):O(n):632.2.当待排记录序列按关键字顺序有序时当待排记录序列按关键字顺序有序时3.3.简单选择排序、堆排序和归并排序的时间简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。性能不随记录序列中关键字的分布而改变。 直接插入排序和起泡排序直接插入排序和起泡排序能达到能达到O(O(n n) )的时的时间复杂度，间复杂度， 快速排序快速排序的时间性能的时间性能蜕化为蜕化为O(O(n n2 2) ) 。各种排序方法时间性能各种排序方法时间性能64指的是排序过程中所需的
33、辅助空间大小指的是排序过程中所需的辅助空间大小1.1.所有的所有的简单排序方法简单排序方法( (包括：直接插入、包括：直接插入、起泡和简单选择起泡和简单选择) ) 和堆排序和堆排序的空间复杂度的空间复杂度为为O(1)O(1)；2.2.快速排序为快速排序为O(logO(logn n) )，为递归程序执行过程中，栈为递归程序执行过程中，栈所需的辅助空间；所需的辅助空间；各种排序方法空间性能各种排序方法空间性能3.3.归并排序归并排序所需辅助空间最多，其空间复杂度为所需辅助空间最多，其空间复杂度为 O(O(n n););4.4.链式基数排序链式基数排序需附设队列首尾指针，则空间复杂需附设队列首尾指针
34、，则空间复杂度为度为 O(O(rdrd) )。65排序方法的稳定性能排序方法的稳定性能 1. 稳定的排序方法指的是，对于两个关键字相等的记稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。之后，没有改变。 2. 当对多关键字的记录序列进行当对多关键字的记录序列进行LSD方法排序时，必方法排序时，必须采用稳定的排序方法。须采用稳定的排序方法。排序之前排序之前 : : Ri(K) Rj(K) 排序之后排序之后 : : Ri(K) Rj(K) 3. 快速排序、堆排序和希尔排序是不稳定的排序方快速
35、排序、堆排序和希尔排序是不稳定的排序方法。法。66例如：例如： 排序前排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 )若排序后得到结果若排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 )则称该排序方法是则称该排序方法是稳定的稳定的;若排序后得到结果若排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 )则称该排序方法是则称该排序方法是不稳定的不稳定的。67排序方法的时间复杂度的下限排序方法的时间复杂度的下限 本章讨论的各种排序方法，除基数排序外，其它方法都是基于基于“比较关键字比较关键字”进进行排序的排
36、序方法。行排序的排序方法。 可以证明， 这类排序法可能达到的最可能达到的最快的时间复杂度为快的时间复杂度为O(nlogn)。 (基数排序不是基于“比较关键字”的排序方法，所以它不受这个限制。)68 例如:对三个关键字进行排序的判定树如下：K1K3K1K2K1K3K2K3K2 K3K2K1K3K1K2K3K3K2K1K2K3K1K3K1K2K1K3K2树上的树上的每一次每一次“比较比较”都是必要的都是必要的;树上的树上的叶子结点包含所有可能情况叶子结点包含所有可能情况。69 一般情况下，对n个关键字进行排序，可能得到的结果有n! 种，由于含n! 个叶子结点的二叉树的深度不小于log2(n!) +
37、1, 则对 n 个关键字进行排序的比较次数至少是 log2(n!) nlog2n (斯蒂林近似公式)。 所以，基于基于“比较关键字比较关键字”进行排序进行排序的的排序方法，可能达到的最快的时间复杂排序方法，可能达到的最快的时间复杂度为度为 O(nlogn)。70 对对外存中数据的读外存中数据的读/ /写是以写是以“数据块数据块”为单位进行的为单位进行的；读读/ /写外存中一个写外存中一个“数据块数据块”的数据所需要的时间为：的数据所需要的时间为： T TI/OI/O = t = tseek seek + t+ tlala + n + n t twmwm 其中其中 t tseek seek 为寻
38、查时间为寻查时间( (查找该数据块所在磁道查找该数据块所在磁道) ) t tlala 为等待为等待( (延迟延迟) )时间时间 n n t twmwm 为传输数据块中为传输数据块中n n个记录的时间。个记录的时间。外部排序外部排序 待排序的记录数量很大，不能一次装入内存，则待排序的记录数量很大，不能一次装入内存，则无法利用前面讨论的排序方法无法利用前面讨论的排序方法71 按可用内存大小，利用内部排序方法，按可用内存大小，利用内部排序方法，构造若干构造若干( ( 记录的记录的) ) 有序子序列有序子序列，通常称外，通常称外存中这些记录有序子序列为存中这些记录有序子序列为 “归并归并”；外部排序的
39、基本过程外部排序的基本过程由相对独立的由相对独立的两个步骤两个步骤组成：组成： 通过通过“归并归并”，逐步扩大逐步扩大 ( (记录的记录的) )有有序子序列的长度序子序列的长度，直至直至外存中外存中整个记录序列整个记录序列按关键字有序按关键字有序为止。为止。72例如：例如：假设有一个含假设有一个含10,000个记录的磁盘个记录的磁盘 文件，而当前所用的计算机一次只文件，而当前所用的计算机一次只 能对能对1000个记录进行内部排序，则个记录进行内部排序，则 首先利用内部排序的方法得到首先利用内部排序的方法得到10个个 初始归并段，然后进行逐趟归并初始归并段，然后进行逐趟归并。假设进行假设进行2
40、路归并路归并(即两两归并即两两归并)，则，则第一趟第一趟由由10个归并段得到个归并段得到5个归并段；个归并段；最后一趟最后一趟归并得到整个记录的有序序列。归并得到整个记录的有序序列。第三趟第三趟由由 3 个归并段得到个归并段得到2个归并段；个归并段；第二趟第二趟由由 5 个归并段得到个归并段得到3个归并个归并段；段；73假设假设“数据块数据块”的大小为的大小为200，即每一次访，即每一次访问外存可以读问外存可以读/写写200个记录。个记录。则对于则对于10,000个记录，处理一遍需访问外存个记录，处理一遍需访问外存100次次(读和写各读和写各50次次)。分析上述外排过程中访问外存分析上述外排过
41、程中访问外存(对外对外存进行读存进行读/写写)的次数：的次数：外部排序的分析外部排序的分析74n求得求得10个初始归并段需访问外存个初始归并段需访问外存100次；次；n每进行一趟归并需访问外存每进行一趟归并需访问外存100次；次；n总计访问外存总计访问外存 100 + 4 100 = 500次。次。外部排序的分析外部排序的分析75 外排总的时间还应包括内部排序外排总的时间还应包括内部排序所需时间和逐趟归并时进行内部归并所需时间和逐趟归并时进行内部归并的时间的时间，显然，除去内部排序的因素，显然，除去内部排序的因素外，外，外部排序的时间取决于逐趟归并外部排序的时间取决于逐趟归并所需进行的所需进行
42、的“趟数趟数”。例如例如，若对上述例子采用，若对上述例子采用5 路归并，路归并，则只需进行则只需进行2趟归并，总的访问外存的趟归并，总的访问外存的次数将压缩到次数将压缩到 100 + 2 100 = 300 次。次。76 一般情况下，假设待排记录序列一般情况下，假设待排记录序列含含 m 个初始归并段，外排时采用个初始归并段，外排时采用 k 路路归并，则归并趟数为归并，则归并趟数为 logkm ，显然，显然，随之随之k的增大归并的趟数将减少，因此的增大归并的趟数将减少，因此对对外排外排而言，通常而言，通常采用多路归并采用多路归并。k 的的大小可选，但需综合考虑各种因素。大小可选，但需综合考虑各种因素。外部排序的分析外部排序的分析77置换选择方法置换选择方法人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。79
