排序算法案例PPT学习教案

1、会计学1排序算法案例排序算法案例2排序的概念排序的概念排序是计算机内经常进行的一种操作，其排序是计算机内经常进行的一种操作，其目的是将一组目的是将一组“无序无序”的记录序列调整为的记录序列调整为“有序有序”的记录序列。的记录序列。例如：将下列关键字序列例如：将下列关键字序列52, 49, 80, 36, 14, 58, 61, 23, 97, 75调整为调整为14, 23, 36, 49, 52, 58, 61 ,75, 80, 97第1页/共79页3假设含假设含n个记录的序列为个记录的序列为 R1, R2, ， Rn 其相应的关键字序列为其相应的关键字序列为 K1, K2, ，Kn 这些关键

2、字相互之间可以进行比较，即在这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系它们之间存在着这样一个关系 ： Kp1Kp2Kpn按此固有关系将上式记录序列重新排列为按此固有关系将上式记录序列重新排列为 Rp1, Rp2, ，Rpn 的操作称作排序。的操作称作排序。排序的概念排序的概念第2页/共79页4内部排序和外部排序内部排序和外部排序若若整个排序过程不需要访问外存整个排序过程不需要访问外存便能便能完成，则称此类排序问题完成，则称此类排序问题为内部排序；为内部排序； 反之，若参加排序的记录数量很大，反之，若参加排序的记录数量很大， 整个序列的排序过程整个序列的排序过程不可能在内存中

3、不可能在内存中 完成完成，则称此类排序问题，则称此类排序问题为外部排序为外部排序。第3页/共79页5待排记录的数据类型定义待排记录的数据类型定义#define MAXSIZE 1000 / 待排顺序表最大长度待排顺序表最大长度typedef int KeyType; / 关键字类型为整数类型关键字类型为整数类型typedef struct KeyType key; / 关键字项关键字项 InfoType otherinfo; / 其它数据项其它数据项 RcdType; / 记录类型记录类型typedef struct RcdType rMAXSIZE+1; / r0闲置闲置 int lengt

4、h; / 顺序表长度顺序表长度 SqList; / 顺序表类型顺序表类型第4页/共79页6有序序列R1.i-1Ri无序序列 Ri.n一趟直接插入排序的基本思想一趟直接插入排序的基本思想有序序列R1.i无序序列 Ri+1.n第5页/共79页7实现实现“一趟插入排序一趟插入排序”分三步进行分三步进行3将Ri 插入插入(复制)到Rj+1的位置上。2将Rj+1.i-1中的所有记录记录均后移后移 一个位置；1在R1.i-1中查找查找Ri的插入位置， R1.j.key Ri.key Rj+1.i-1.key；第6页/共79页8直接插入排序直接插入排序第7页/共79页9void InsertionSort

5、( SqList &L ) / 对顺序表 L 作直接插入排序。 for ( i=2; i=L.length; +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; / 插入到正确位置第8页/共79页10直接插入排序时间分析直接插入排序时间分析最好的情况（关键字在记录序列中顺序有序）：最好的情况（关键字在记录序列中顺序有序）：“比较比较”的次数：的次数：最坏的情况（关键字在记录序

6、列中逆序有序）：最坏的情况（关键字在记录序列中逆序有序）：“比较比较”的次数：的次数：112nni02) 1)(4() 1(2nnini“移动移动”的次数：的次数：“移动移动”的次数：的次数：2) 1)(4() 1(2nnini第9页/共79页11 因为因为R1.i-1 R1.i-1 是一个按关键字有是一个按关键字有序的有序序列，则可以序的有序序列，则可以利用折半查找实利用折半查找实现现“在在R1.i-1R1.i-1中中查找查找RiRi的的插入位插入位置置”，如此实现的插入排序为，如此实现的插入排序为折半插入折半插入排序。排序。折半插入排序折半插入排序第10页/共79页1214 36 49 5

7、2 80 58 61 23 97 75ilowhighmmlowlowmhigh14 36 49 52 58 61 80 23 97 75ilowhighmhighmhighmlow例如:再如:插入位置插入位置L.rL.r第11页/共79页13void BiInsertionSort ( SqList &L ) / BInsertSort在在 L.r1.i-1中折半查找插入位置；中折半查找插入位置；for ( i=2; i=high+1; -j ) L.rj+1 = L.rj; / 记录后移L.rhigh+1 = L.r0; / 插入第12页/共79页14low = 1; high = i-1

8、;while (low=high) m = (low+high)/2; / 折半if (L.r0.key L.rm.key) high = m-1; / 插入点在低半区else low = m+1; / 插入点在高半区第13页/共79页15 希尔排序希尔排序 基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整。 所谓“宏观”调整，指的是，“跳跃式”的插入排序。 具体做法为：第14页/共79页16 将记录序列分成若干子序列，分别对每个子序列进将记录序列分成若干子序列，分别对每个子序列进行插入排序。行插入排序。 其中，其中，d d 称为增量，它的值在排序过程中从大到小逐称为增量，它的值在排

9、序过程中从大到小逐渐缩小，直至最后一趟排序减为渐缩小，直至最后一趟排序减为 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 希尔排序希尔排序第15页/共79页17例如：例如：16 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

10、 16 25 31 30 47 36第三趟希尔排序，设增量第三趟希尔排序，设增量 d=1d=1 9 11 12 16 18 23 25 30 31 36 47 第16页/共79页18void ShellInsert ( SqList &L, int dk ) for ( i=dk+1; i=n; +i ) if ( L.ri.key0&(L.r0.keyL.rj.key); j-=dk) L.rj+dk = L.rj; / 记录后移，查找插入位置 L.rj+dk = L.r0; / 插入 / if / ShellInsert第17页/共79页19void ShellSort (SqList &

11、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; /记下进行交换的记录位置 /iffor (j = 1; j i; j+)lastExchangeIndex = 1;第21页/共79页23最好的情况（关键字在记录序列中顺序有序）：最好的情况（关键字在记录序列中顺序有序）： 只需进行一趟起

12、泡只需进行一趟起泡“比较比较”的次数：的次数：最坏的情况（关键字在记录序列中逆序有序）：最坏的情况（关键字在记录序列中逆序有序）： 需进行需进行n-1趟起泡趟起泡“比较比较”的次数：的次数：0“移动移动”的次数：的次数：“移动移动”的次数：的次数：n-12) 1() 1(2nnini2) 1(3) 1(32nnini冒泡排序时间分析冒泡排序时间分析第22页/共79页24一趟快速排序一趟快速排序目标：目标：找一个记录，以它的关键字作为“枢轴枢轴”，凡其关键字小于枢轴关键字小于枢轴的记录均移动至该记录之前移动至该记录之前，反之，凡关键字大于关键字大于枢轴枢轴的记录均移动至该记录之后移动至该记录之后

13、。致使一趟排序一趟排序之后，记录的无序序列Rs.t将分割成两部分分割成两部分：Rs.i-1和Ri+1.t，且 Rj.key Ri.key Rj.key (sji-1) 枢轴枢轴 (i+1jt)。第23页/共79页2552 49 80 36 14 58 61 97 23 75stlowhigh设设 Rs=52 为枢轴为枢轴 将 Rhigh.key 和 枢轴的关键字进行比较，要求Rhigh.key 枢轴的关键字 将 Rlow.key 和 枢轴的关键字进行比较，要求Rlow.key 枢轴的关键字high23low80high14low52例如例如R052lowhighhighhighlow第24页/

14、共79页26int 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; / 返回枢轴所在位置 / Partition第25页/共79页27int Partition (RedType R, int low, int high) / Partition R0 = Rlow; pivotk

15、ey = Rlow.key; / 枢轴 while (lowhigh) while(low=pivotkey) - high; / 从右向左搜索Rlow = Rhigh;while (lowhigh & Rlow.key=pivotkey) + low; / 从左向右搜索Rhigh = Rlow;Rlow = R0; return low;第26页/共79页28快速排序快速排序 首先对无序的记录序列进行“一次划分一次划分”，之后分别分别对分割所得两个子序列“递归递归”进行快速进行快速排序排序。无无 序序 的的 记记 录录 序序 列列无序记录子序列无序记录子序列(1)(1)无序子序列无序子序列(

16、2)(2)枢轴枢轴一次划分一次划分分别进行快速排序分别进行快速排序第27页/共79页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); / 对高子序列递归排序第28页/共79页30快速排序的时间分析快速排序的时间分析假设

17、假设一次划分所得枢轴位置一次划分所得枢轴位置 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)第29页/共79页31nkavgavgavgknTkTnCnnT1)() 1(1)(设 Tavg(1)b则可得结果：

18、) 1ln() 1)(22()(nncbnTavg结论结论: 快速排序的时间复杂度为快速排序的时间复杂度为O(nlogn)由此可得快速排序所需时间的平均值为：第30页/共79页32 若待排记录的初始状态为按关键字有序若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。快速排序的时间分析快速排序的时间分析第31页/共79页33简单选择排序简单选择排序假设排序过程中，待排记录序列的状态为：有序序列R1.i-1无序序列 Ri.n 第 i 趟简单选择排序从中选出关键字最小的记录有序序列R1.i无序序列 Ri+1.n第32页/共79页34

19、简单选择排序简单选择排序第33页/共79页35void SelectSort (Elem R, int n ) / 对记录序列R1.n作简单选择排序。 for (i=1; i0; -i ) HeapAdjust ( H.r, i, H.length ); / 建大顶堆for ( i=H.length; i1; -i ) H.r1H.ri; / 将堆顶记录和当前未经排序子序列 / H.r1.i中最后一个记录相互交换 HeapAdjust(H.r, 1, i-1); / 对 H.r1 进行筛选第38页/共79页4098814973556412362740例如例如:是最大堆是最大堆12但在 98 和

20、 12 进行互换之后，它就不不是堆了，因此，需要对它进行“筛选”。98128173641298比较比较比较第39页/共79页41void HeapAdjust (RcdType &R, int s, int m) / 已知 Rs.m中记录的关键字除 Rs 之外均 / 满足堆的特征，本函数自上而下调整 Rs 的 / 关键字，使 Rs.m 也成为一个大顶堆 / HeapAdjustrc = Rs; / 暂存 Rs for ( j=2*s; j= Rj.key ) break; / 再作“根”和“子树根”之间的比较， / 若“=”成立，则说明已找到 rc 的插 / 入位置 s ，不需要继续往下调整R

21、s = Rj; s = j; / 否则记录上移，尚需继续往下调整if ( jm & Rj.keyRj+1.key ) +j; / 左/右“子树根”之间先进行相互比较 / 令 j 指示关键字较大记录的位置第41页/共79页43建堆是一个从下往上进行建堆是一个从下往上进行“筛选筛选”的过程的过程40554973816436122798例如例如: : 排序之前的关键字序列为排序之前的关键字序列为123681734998817355 现在，左现在，左/ /右子树都已经调整为堆，最后只要右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个调整根结点，使整个二叉树是个“堆堆”即可。即可。984940

22、64361227第42页/共79页44堆排序的时间复杂度分析堆排序的时间复杂度分析1. 对深度为对深度为 k 的堆，的堆，“筛选筛选”所需进行的关键字所需进行的关键字比较的次数至多为比较的次数至多为2(k-1)；3. 调整调整“堆顶堆顶” n-1 次，总共进行的关键次，总共进行的关键 字比较的次数不超过字比较的次数不超过 2 ( log2(n-1) + log2(n-2) + +log22) 2n( log2n ) 因此，因此，堆排序的时间复杂度为堆排序的时间复杂度为O(O(n nloglogn n) )。2. 对对 n 个关键字，建成深度为个关键字，建成深度为h(= log2n +1)的堆，

23、的堆，所需进行的关键字比较的次数至多所需进行的关键字比较的次数至多 4n；第43页/共79页45 通常采用的是通常采用的是2-2-路归并路归并排序。即：排序。即：将两个将两个位置相邻的记录有序子序列位置相邻的记录有序子序列归并为一个记录的有序序列。归并为一个记录的有序序列。有有 序序 序序 列列 Rl.n有序子序列有序子序列 Rl.m 有序子序列有序子序列 Rm+1.n归并排序归并排序第44页/共79页46void Merge (RcdType SR, RcdType &TR, int i, int m, int n) / 将有序的记录序列 SRi.m 和 SRm+1.n / 归并为有序的记录

24、序列 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+; 第45页/共79页47if (i=m) TRk.n = SRi.m; / 将剩余的 SRi.m 复制到 TRif (j=n) TRk.n = SRj.n; / 将剩余的 SRj.n 复制到 TR第46页/共79页48归并排序的算法归并排序的算法如果记录无序序列如果记录无序序列 Rs.t 的两部分的两部分 Rs. (s+t)/2 和 R (s+t

25、)/2 +1.t分别按关键字有序，分别按关键字有序， 则利用上述归并算法很容易将它们归则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列。并成整个记录序列是一个有序序列。 由此，应该先分别对这两部分进行由此，应该先分别对这两部分进行 2-路归并排序。路归并排序。第47页/共79页49例如：例如：52, 23, 80, 36, 68, 14 (s=1, t=6) 52, 23, 80 36, 68, 14 52, 2380 52 23, 52 23, 52, 8036, 6814366836, 6814, 36, 68 14, 23, 36, 52, 68, 80 23第48页/共7

26、9页50void Msort ( RcdType SR, RcdType &TR1, int s, int t ) / 将SRs.t 归并排序为 TR1s.t if (s= =t) TR1s=SRs; else / Msort 第49页/共79页51m = (s+t)/2; / 将SRs.t平分为SRs.m和SRm+1.tMsort (SR, TR2, s, m); / 递归地将SRs.m归并为有序的TR2s.mMsort (SR, TR2, m+1, t); /递归地SRm+1.t归并为有序的TR2m+1.tMerge (TR2, TR1, s, m, t); / 将TR2s.m和TR2m+

27、1.t归并到TR1s.t第50页/共79页52void MergeSort (SqList &L) / 对顺序表 L 作2-路归并排序 MSort(L.r, L.r, 1, L.length); / MergeSort容易看出，对 n 个记录进行归并排序的时间复杂度为(nlogn)。即： 每一趟归并的时间复杂度为 O(n)， 总共需进行 log2n 趟。第51页/共79页53第52页/共79页54基数排序是一种借助基数排序是一种借助“多关键字排多关键字排序序”的思想来实现的思想来实现“单关键字排序单关键字排序”的内部排序算法。的内部排序算法。基数排序基数排序第53页/共79页55多关键字的排序

28、多关键字的排序 n 个记录的序列个记录的序列 R1, R2, ，Rn对关键字对关键字 (Ki0, Ki1, ,Kid-1) ) 有序有序是指： 其中其中: : K0 被称为被称为 “最主最主”位关键字位关键字Kd-1 被称为被称为 “最次最次”位关键字位关键字 对于序列中任意两个记录 Ri 和 Rj(1ijn) 都满足满足下列(词典词典)有序有序关系： (Ki0, Ki1, , ,Kid-1) ) (Kj0, Kj1, , ,Kjd-1) )第54页/共79页56 先对先对K0进行排序进行排序，并按 K0 的不同值将记录序列分成若干子序列之后，分别对 K1 进行排序，.， 依次类推，直至最后对

29、最次位关键字排序完直至最后对最次位关键字排序完成为止成为止。最高位优先最高位优先MSD法法第55页/共79页57 先对 Kd-1 进行排序，然后对 Kd-2 进行排序，依次类推，直至对最主位直至对最主位关键字关键字 K0 排序完成为止排序完成为止。最低位优先最低位优先LSD法法第56页/共79页58链式基数排序链式基数排序假如多关键字的记录序列中，每个关键字的假如多关键字的记录序列中，每个关键字的取值范围相同，则按取值范围相同，则按LSD法进行排序时，可以法进行排序时，可以采用采用“分配分配- -收集收集”的方法，其好处是不需要进的方法，其好处是不需要进行关键字间的比较。行关键字间的比较。对于

30、数字型或字符型的对于数字型或字符型的单关键字单关键字，可以，可以看看成成是由多个数位或多个字符构成的是由多个数位或多个字符构成的多关键字多关键字，此时可以此时可以采用采用这种这种“分配分配- -收集收集”的办法的办法进行排进行排序序，称作基数排序法称作基数排序法。第57页/共79页59链式基数排序链式基数排序第58页/共79页601 1、待排序记录以指针相链，构成一个链表；、待排序记录以指针相链，构成一个链表； 2 2、“分配分配” 时，按当前时，按当前“关键字位关键字位”所取值，所取值，将记录分配到不同的将记录分配到不同的 “链队列链队列” 中，每个中，每个队列中记录的队列中记录的 “关键字

31、位关键字位” 相同；相同；3 3、“收集收集”时，按当前关键字位取值从小到时，按当前关键字位取值从小到大将各队列首尾相链成一个链表大将各队列首尾相链成一个链表; ;4 4、对每个关键字位均重复、对每个关键字位均重复 2) 2) 和和 3) 3) 两步。两步。链式基数排序链式基数排序第59页/共79页61 基数排序的时间复杂度为基数排序的时间复杂度为O(d(n+rd)其中：分配为其中：分配为O(n) 收集为收集为O(rd)(rd为为“基基”) d为为“分配分配-收集收集”的趟数的趟数堆排序的时间复杂度分析堆排序的时间复杂度分析第60页/共79页62各种排序方法时间性能各种排序方法时间性能1.1.

32、平均的时间性能平均的时间性能基数排序基数排序时间复杂度为时间复杂度为 O(O(n nloglogn n) )：快速排序、堆排序和归并排序快速排序、堆排序和归并排序时间复杂度为时间复杂度为 O(n2)O(n2)：直接插入排序、起泡排序和直接插入排序、起泡排序和简单选择排序简单选择排序时间复杂度为时间复杂度为 O(n):O(n):第61页/共79页632.2.当待排记录序列按关键字顺序有序时当待排记录序列按关键字顺序有序时3.3.简单选择排序、堆排序和归并排序的时间简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。性能不随记录序列中关键字的分布而改变。 直接插入排序和起泡排

33、序直接插入排序和起泡排序能达到能达到O(O(n n) )的时的时间复杂度，间复杂度， 快速排序快速排序的时间性能的时间性能蜕化为蜕化为O(O(n n2 2) ) 。各种排序方法时间性能各种排序方法时间性能第62页/共79页64指的是排序过程中所需的辅助空间大小指的是排序过程中所需的辅助空间大小1.1.所有的所有的简单排序方法简单排序方法( (包括：直接插入、包括：直接插入、起泡和简单选择起泡和简单选择) ) 和堆排序和堆排序的空间复杂度的空间复杂度为为O(1)O(1)；2.2.快速排序为快速排序为O(logO(logn n) )，为递归程序执行过程中，栈为递归程序执行过程中，栈所需的辅助空间；

34、所需的辅助空间；各种排序方法空间性能各种排序方法空间性能3.3.归并排序归并排序所需辅助空间最多，其空间复杂度为所需辅助空间最多，其空间复杂度为 O(O(n n););4.4.链式基数排序链式基数排序需附设队列首尾指针，则空间复杂需附设队列首尾指针，则空间复杂度为度为 O(O(rdrd) )。第63页/共79页65排序方法的稳定性能排序方法的稳定性能 1. 稳定的排序方法指的是，对于两个关键字相等的记稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。之后，没有改变。 2. 当对多关键字的记

35、录序列进行当对多关键字的记录序列进行LSD方法排序时，必方法排序时，必须采用稳定的排序方法。须采用稳定的排序方法。排序之前排序之前 : : Ri(K) Rj(K) 排序之后排序之后 : : Ri(K) Rj(K) 3. 快速排序、堆排序和希尔排序是不稳定的排序方快速排序、堆排序和希尔排序是不稳定的排序方法。法。第64页/共79页66例如：例如： 排序前排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 )若排序后得到结果若排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 )则称该排序方法是则称该排序方法是稳定的稳定的;若排序后得到结果若排序

36、后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 )则称该排序方法是则称该排序方法是不稳定的不稳定的。第65页/共79页67排序方法的时间复杂度的下限排序方法的时间复杂度的下限 本章讨论的各种排序方法，除基数排序外，其它方法都是基于基于“比较关键字比较关键字”进进行排序的排序方法。行排序的排序方法。 可以证明， 这类排序法可能达到的最可能达到的最快的时间复杂度为快的时间复杂度为O(nlogn)。 (基数排序不是基于“比较关键字”的排序方法，所以它不受这个限制。)第66页/共79页68 例如:对三个关键字进行排序的判定树如下：K1K3K1K2K1K3K2K3K2 K3

37、K2K1K3K1K2K3K3K2K1K2K3K1K3K1K2K1K3K2树上的树上的每一次每一次“比较比较”都是必要的都是必要的;树上的树上的叶子结点包含所有可能情况叶子结点包含所有可能情况。第67页/共79页69 一般情况下，对n个关键字进行排序，可能得到的结果有n! 种，由于含n! 个叶子结点的二叉树的深度不小于log2(n!) +1, 则对 n 个关键字进行排序的比较次数至少是 log2(n!) nlog2n (斯蒂林近似公式)。 所以，基于基于“比较关键字比较关键字”进行排序进行排序的的排序方法，可能达到的最快的时间复杂排序方法，可能达到的最快的时间复杂度为度为 O(nlogn)。第6

38、8页/共79页70 对对外存中数据的读外存中数据的读/ /写是以写是以“数据块数据块”为单位进行的为单位进行的；读读/ /写外存中一个写外存中一个“数据块数据块”的数据所需要的时间为：的数据所需要的时间为： T TI/OI/O = t = tseek seek + t+ tlala + n + n t twmwm 其中其中 t tseek seek 为寻查时间为寻查时间( (查找该数据块所在磁道查找该数据块所在磁道) ) t tlala 为等待为等待( (延迟延迟) )时间时间 n n t twmwm 为传输数据块中为传输数据块中n n个记录的时间。个记录的时间。外部排序外部排序 待排序的记录数量很大，不能一次装入内存，则待排序的记录数量很大，不能一次装入内存，则无法利用前面讨论的排序方法无法利用前面讨论的排序方法第69页/共79页71 按可用内存大小，利用内部排序方法，按可用内存大小，利用内部排序方法，构造若干构造若干( ( 记录的记录的) ) 有序子序列有序子序列，通常称外，通常称外存中这些记录有序子序列为存中这些记录有序子序列为 “归并归并”；外部排序的基本过程外部排序的基本过程由相对独立的由相对独立的两个步骤两个步骤组成：组成： 通过通过“归并归并”，逐步扩大逐步扩大 ( (记录的记录的) )有有序子序列的