数据结构-清华大学-殷人昆.docx

第七章排序从来处来往去处去次序之美美在规矩利在行方概述插入排序 交换排序 选择排序 归并排序 表排序 基数排序各种内排序方法的比较 外排序概述 排序：将一组杂乱无章的数据按一定的规律顺次 排列起来。 数据表(datalist):它是待排序数据记录的有限集 合。 排序码(key):通常数据记录有多个属性域，即多 个数据成员组成，其中有一个属性域可用来区分 记录，作为排序依据。该域即为排序码。口每个数据表用哪个属性域作为排序码，要视具 体的应用需要而定。本章所涉及排序码的值允许重复。排序算法的稳定性：如果在记录序列中有两个记 录ri和5,它们的排序码值kij = kj,且在排序 之前，记录门“排在rj前面。如果在排序之后，记 录邙仍在记录的前面，则称这个排序方法是 稳定的,否则称这个排序方法是不稳定的。内排序与外排序内排序是指在排序期间数据记录全部存放在内 存的排序；外排序是指在排序期间全部记录个数太多，不 能同时存放在内存，必须根据排序过程的要求, 不断在内、外存之间移动的排序。排序的时间开销：排序的时间开销是衡量算法好 坏的最重要的标志。内排序的时间开销可用算法 执行中的排序码比较次数与数据移动次数来衡量; 外排序的时间开销要看读写外存的次数。-算法运行时间代价的大略估算一般都按平均情况 进行估算。对于那些受记录排序码序列初始排列 及记录个数影响较大的，需要按最好情况和最坏 情况分别进行估算。-算法执行时所需的附加存储：评价算法好坏的另 一标准。从排序过程中数据的总体变化趋势来看，排序方 法的处理可以分为两大类。(1)有序区增长：将数据表分成有序区和无序区，在 排序过程中逐步扩大有序区，缩短无序区，直到 有序区扩大到整个数据表为止。如插入排序、选 择排序、起泡排序、堆排序、归并排序等。(2)有序程度增长：数据表不能明确区分有序区和无 序区，随着排序过程的执行，逐步调整表中元素 的排列，使得表中的有序程度不断提高，直到完 全有序。如快速排序、希尔排序、基数排序等。待排序数据表的结构定义const int DefaultSize = 100; typedef int DataType;typedef struct Element DataType key; otherdata;表元素定义排序码其他数据成员）；typedef struct dataList 数据表定义Element elemDefaultSize; 存宿羲组int n;前元素个数插入排序(Insert Sorting)基本方法是：每步将一个待排序的记录，按其排序码值的大小，插入到前面已经排好序的一组记录的适当位置上,直到记录全部插入为止。直接插入排序(Insert Sort)直接插入排序的基本思想是：当插入第个记录时,前面的elem0h,elemi-l已经排好序。这时，用的排序码与的排序码顺序比较，找到插入位置即将插入,原来位置上的记录向后顺移。”101234567t 25 > 21 ,无需移动t49>25,无需移动t 37 < 5252, 49后移直接插入排序的算法void InsertSort ( dataList& L ) Element w； inti"for (i = 1; i < L.n; i+ )插入n-1 趟if ( L.elemi.key < L.elemi-l.key ) w = L.elemi; L.elemi = L.elemi-1;for(j = i-l; j>O;j)从后向前比较if ( w.key < L.elemj-l.key ) 比j-l元素小L.elemj = L.elemj-1; 让j-1 元素后移 else break;L.elemj = w;法分析 设待排序记录个数为，则该算法的主程序执行 趟。排序码比较次数和记录移动次数与记录 排序码的初始排列有关。 最好情况下，排序前记录已按排序码的值从小到 大有序，每趟只需与前面有序记录序列的最后一 个记录比较1次，移动0次记录，总的排序码比 较次数为"-1,记录移动次数为Oo 最坏情况下，第i趟时第，个记录必须与前面i 个记录都做排序码比较，并且每做1次比较就要 做1次数据移动。 因此，在最坏情况下，总排序码比较次数KCN和 记录移动次数RMN分别为n-lKCN = i =双11 - D。- n2/29i=lRMN = £ (i + 2) = (n + 4)(n -1)/2。n2/2 在平均情况的排序码比较次数和记录移动次数 约为4/4。因此，直接插入排序的时间复杂度为 O(n2)o 直接插入排序是一种稳定的排序方法。 直接插入排序需要一个附加记录暂存待插记录。折半插入排序(Binary Insertsort)-折半插入排序的基本思想是：设在顺序表中有一 个记录序列 elem09 eleml,elemw-lo 其中, elem05 eleml,elemi-l是已经排序的数据 记录。在插入时，不是利用顺序查找从后 向前寻找插入位置，而是利用折半查找法寻找elemf的插入位置。折半插入排序的算法void BinaryInsSort ( dataList& L ) Element w; int i, k, left, right, mid; for (i = 1; i < L.n; i+ ) 159-15left = 0; right = i-1; w = L.elemi;while (left <= right) 在内寻找elemi插入位置mid = (left+right )/2;中间位置if ( w.key < L.elemmid.key ) 小于中点值right = mid-1;*蓊区间else left = mid+1;右缩区间)for ( k = i-1; k >= left; k-)L.elemk+1 = L.elemk;空出 left 位置L.elemleft = w; / for算法分析- 折半搜索比顺序搜索查找快，所以折半插入排序 就平均性能来说比直接插入排序要快。- 它所需的排序码比较次数与待排序记录序列的初 始排列无关,仅依赖于记录个数。- 在插入第，个记录时，需要经过|_1吗，+1次排序码比较，才能确定它应插入的位置。- 因此，将个记录元素（为推导方便，设为 =2匕 k = log2n ）,折半插入排序所进行的排序码比较 次数为：n-1*1峭+1)=!+2+土+3 h卜k+k 1 1 K i=l2°21222k-1= 1*2。+2"+3*22+ + k*2i= (k-l)* 2k +1 = n(log2n-l) + l = nlog2n-n + l 这是折半查找算法分析得到的结果。折半查找的 时间复杂度为O(nk)g2n)，这是指排序码比较次数 的时间开销，但记录移动次数就不同了。 折半插入排序的记录移动次数比直接插入排序多 一点，依赖于记录元素的初始排列。 折半插入排序是一个稳定的排序方法。 折半插入排序需要一个附加记录暂存待插记录。希尔排序(Shell Sort).希尔排序方法又称为缩小增量排序。.该方法的基本思想是：设待排序记录序列有n个记 录，首先取一个整数gap vn作为间隔，将全部记录 分为gap个子序列，所有距离为gap的记录放在同 一个子序列中，在每一个子序列中分别施行直接插 入排序。然后缩小间隔gap,例如取gap = gap/2，重复上 述的子序列划分和排序工作。直到最后取gap = 1, 将所有记录放在同一个序列中排序为止。16V21.21 后移08 < 25. 25后移52 > 49.无需移动37 > 25.无需移动01234567i = 2 gap=249 > 1621 < 4952 > 49无需移动 49后移无需移动25* > 0825 = 2537 > 25无需移动无需移动无需移动结果i = 3 gap=l国同闻同012316 <0816后移国园国国国国阂国456725 <4937 < 5249后移 52, 49后移国同同阂开始时gap的值较大，子序列中的记录较少，排 序速度较快；随着排序进展，gap值逐渐变小， 子序列中记录个数逐渐变多，由于前面工作的基 础，大多数记录已基本有序，所以排序速度仍然 很快。希尔排序的算法void ShellSort ( dataList& L ) Elementw； gap = L.n / 2;while ( gap != 0 ) 宿环，直到gap为零for (i = gap; i < L.n; i+ ) w = L.elemi;直接插入排序for (j = i; j >= gap; j = j-gap )if ( w.key < L.elemj - gap .key )L.elemj = L.elemj-gap;else break;L.elemj = w;)gap = gap / 2;)算法分析 开始时gap的值较大，子序列中的记录较少，排 序速度较快；随着排序进展，gap值逐渐变小， 子序列中记录个数逐渐变多，由于前面工作的基 础，大多数记录已基本有序，所以排序速度仍然 很快。 gap取法有多种。最初shell提出取gap = |_n/2， gap = Lgap/2j,直至!gap = lo knuth 提出取 gap = gap/3+L 对特定的待排序记录序列，可以准确地估算排序 码的比较次数和记录移动次数。 但想要弄清排序码比较次数和记录移动次数与增 量选择间的依赖关系，并给出完整的数学分析， 还没有人能够做到。Knuth利用大量实验统计资 料得出：当n很大时，排序码平均比较次数和记 录平均移动次数约在ni25到1.6出25的范围内。 后来Hibbard提出一个稍微不同的增量序列，让 gap = 2T7, 3 J 最坏情况下结果更好，运行时间在理论上证明可达到O(n3/2),但实 际模拟结果可达到O(n5”。 希尔排序是个不稳定的排序方法。交换排序(Exchange Sort) 基本思想是两两比较待排序记录的排序码，如发 生逆序(即排列顺序与排序后的次序正好相反)则 交换之。直到所有记录都排好序为止。起泡排序(Bubble Sort) 起泡排序的基本思路是：设待排序记录序列中的记录个数为。最多作“T趟起泡，2,，n-lo在第，趟.中从后向前,j =一2,，i,顺次两两比较和如果发生逆序, 即elemj-l >elemj,则 交换elemj-l和elemj。01234567同国国国国同阈同Exchang=lExchang=lExchang=lExchang=lExchange起泡排序的算法void BubbleS ort ( dataList& L ) int i = 1, j; int exchange = 1;while (i < L.n && exchange ) exchange = 0;标志置为0,假定未交换for (j = L.n-l; j >= i; j )if (L.elemj-l.key > L.elemj.key ) 逆序Swap (L.elemj-1, L.elemj);/交装exchange = 1; 标志置为1,有交换)i+；算法分析 第i趟对待排序记录序列进行排序，结果将该序列中排序码最小 的记录交换到序列的第一个位置其他记录 也都向排序的最终位置移动。在个别情形，记录可 能在排序中途向相反的方向移动。 最多做趟起泡就能把所有记录排好序。 起泡排序的时间代价受记录的初始排列影响。在 记录的初始排列已经按排序码的值从小到大排好 序时，此算法只执行一趟起泡，做次排序码 比较，不移动记录。这是最好的情形。 最坏情形是算法执行趟起泡，第，趟(iwiv) 做次排序码比较，执行次记录交换。像所 有记录在一开始就已经按其排序码值逆序即为这 种情况。因此，在最坏情形下总的排序码比较次 数KCN和记录移动次数RMN为：KCN = 2(n-i) = -n(n-l)i=l2RMN = 32L(n-i) = -n(n-l) 起泡排序是一本居定的排序方法。 起泡排序需要一个附加记录作为交换记录使用。快速排序（Quick Sort）.快速排序又称分区排序，其基本思路是：任取待 排序记录序列中的某个记录（例如取第一个记录） 作为基准，按照该记录的排序码值的大小，将整 个记录序列划分为左右两个子序列：左侧子序列中所有记录的排序码值都小于或等 于基准记录的排序码值；右侧子序列中所有记录的排序码值都大于基准 记录的排序码值。 基准记录则排在这两个子序列中间（这也是该记录 最终应安放的位置）。然后分别对这两个子序列重复施行上述方法, 到所有的记录都排在相应位置上为止。下图是对一组排序码的一趟划分的例子。逆向正向012345it-16 <21 t67FA逆向正向m 0123456712345 | | 1593667逆向El it49 >21 J j快速排序一趟划分的算法int Partiton 1 ( dataList& L, int i, int j) Element w = L.elemi;while (i < j ) while (i < j && L.elemj.key >= w.key ) j一一;if (i < j) L.elemi = L.elemfj; i+;逆向，小于基准者左移while (i < j && L.elemi.key <= w.key ) i+;) L.elemj = L.elemi; j ;正向，大于基准者右移)L.elemi = w;/基准记录就位return i;返回基准位置,即排序区间划分点快速排序的递归算法void Quicksort ( dataList& L, int left, int right) if (left < right) int pivotpos = Partition 1 (L, left, right); 划分Quicksort ( L, left, pivotpos-1 );Quicksort ( L, pivotpos+1, right); 设待排序区间为Lleft.right,以w = Lleft作 为划分的基准。用指针i = left+1和j = right从 区间的左端和右端开始向中间检查：(1)若Lj>=w,让j-，重复这一步，直到遇到 Lj vw的记录容止；(2)若Liv=w,让i+,重复这一步，直到遇到 Li >w的记录停止；(3)若 ivj,则交换 Li与 Lj,且令 i+, j, 然后继续重复以上(1), (2), (3)步，向中间靠拢，直到i = j为止。交换Lj与Lleft后，基准排在 位置j,此即划分点，它左边子区间记录的排序 码都比它的排序码小，右边子区间记录的排序码 都比它的排序码大。 此算法比前一个划分算法整齐，算法时间复杂度 都是O(n),但由于它每一次交换需要3次数据传 递，比前一个算法需要数据传送的次数多。而前 一个划分算法的数据传送次数已经达到了最少。 下面是一个使用此算法进行划分的示例。同同国同同国同囱01234567- ii j 425 >2108 < 2125, 08交换01234567i ii j <49 >2116<2149,16交换iiij 一i=j与基准对换01234567int Partition2 ( DataList& L, int left, int right) if (left < right) int i = left+1, j = right;do while (i <= j &&反向检测L.elemlow.key <= L.elemj.key ) j-;while (i < j &&正向检测L.elemi.key <= L.elemlow.key ) i+; if(i<j) Swap (L, i,j); i+; j-; while (i < j);交换if (j != low ) Swap ( L, low, j); 交换 /* end of if (left < right) */ return i;.算法的思路是：以待排序序列的第一个元素作为 比较基准，然后从左向右一趟扫描过去，凡是比 基准小的都交换到左边，最后对基准再做一次交 换，得到划分结果。下面给出用这个算法一趟划分的结果。同国同国同同国同01234567I k i I f -> f21<25 21<4921V25* 21>16,16继续继续继续与25交换4 1，"3 F21>08, 08与49交换2K52 2K37继续 继续34567012ik基准21与最后交换到前面 的比21小的元素08交换国园固国国国同时01234567k-一趟划分的算法如下所示。这三种划分算法的时 间复杂度都是O(n),随序列不同，差别不大。int Partitions ( dataList& L, int low, int high ) int i, k = low;for (i =low+1; i <= high; i+ )if ( L.elemi.key < L.elemlow.key ) k+;if(k!=i)Swap(L, i,k);)交换小于基准的元素到左边去if ( k != low ) Swap ( L, low, k);基准就位return k;)；返回基准元素位置4, 7, 5, 6,3,1,2PartitionlPartitionlPartitions比较次数101111移动次数142124递归深度2334, 7, 5, 6, 2, 3,1PartitionlPartitionlPartitions比较次数111012移动次数161818递归深度3234, 6, 5, 7, 3,1,2PartitionlPartitionlPartitions比较次数11910移动次数172118递归深度322算法分析 算法quicksort是一个递归的算法，其递归树如图所 不。 这是快速排序算法一次次调用partition算法得到 的结果。 快速排序执行排序的趟数取决于递归树的高度。 如果每次划分能将序列划分为长度接近相等的子 序列，则下一步将是对两个长度减半的子序列进 行排序，这是最理想的情况。 在n个元素的序列中，对基准元素定位所需时间 为O(n)。若设T(n)是对n个元素的序列进行排序 所需的时间，而且每次对一个记录正确定位后， 正好把序列划分为长度相等的两个子序列，则T(n)<cn + 2T(n/2)/ c 是一个常数<cn + 2(cn/2 + 2T(n/4) = 2cn + 4T(n/4)<2cn + 4(cn/4 +2T(n/8) = 3cn + 8T(n/8)W cn log2n + nT(l) = O(nlog2n ) 可以证明，函数quicksort的平均计算时间也是 O(nlog2n)0实验结果表明：就平均计算时间而言, 快速排序是所有内排序方法中最好的一个。 快速排序是递归的，需要有一个栈存放每层递归 调用时的指针和参数。.最大递归调用层次数与递归树高度一致，理想情 况为log2(n+l)1。故栈的存储开销为OQogz11)。 最坏情况是待排序记录序列已经按其排序码从小 到大排好序。 在最坏的情况下，其递归树成为单支树，每次划分只得 到一个比上一次少一个记录的子序列。总的排序码比 较次数将达(n-i) = 1n(n-l) i=l2n2X2 附加存储(递归栈)的开销也将达到0(11)。 快速排序是一种不稳定的排序方法，其原因与希尔排 序类似，都是因为出现相隔一段距离传送数据。 快速排序也可以改为非递归算法。在把待排序区间划 分为两个子区间后，利用栈保存其中一个子区间的端 点，再对另一个子区间快速排序。以后再从栈中恢复该子区间执行快速排序。159-52选择排序.选择排序的基本思想是：口每''趟（例如第i趟,i = 0,1,一2）在后面一i 个待排序记录序列中选出排序码值最小的记录， 作为有序记录序列的第，个记录。待到第-2趟 作完，待排序记录只剩下1个，就不用再选了。选择排序的每一趟可把有序区扩大，直到-1趟 后即可把有序区扩大到整个待排序序列。简单选择排序(Select Sort)简单选择排序的基本步骤是： 在一组记录elemi中选择具有 最小排序码的记羡；若它不是这组记录中的第一个记录，则将它 与这组记录中的第一个记录对调；在这组记录中剔除这个具有最小排序码值的 记录。在剩下的记录elemi+1 elemn-1 中重复执行第、步，直到剩余记录只有 一个为止。最小者16 交换25,16最小者08 交换21,08> k 最小者21 159-55 交换 “RI不交换同同同同同同阈同1 = 4ik 最小者25本交换1 = 5最小者37 iWk> k交换49,37国同同同国同同国1 = 6最小者49 用左一山交换49,52国同国固国同国阈i = l时选择最小记录的过程画园同国固团012345ik最初假定Lk (k = i)最小5女指示当 0 前序列中1234ik j 49 >25, j+团连国国同国国国除 J I25* > 25, j+词国同国国国16 <25, j+词国同国同画159-5821 >16简单选择排序的算法void SelectSort ( dataList& L) int i,j,k;for (i = 0; i < L.n-1; i+ ) k二i;选择具有最小排序码值的记录for (j = i+l; j <L,n; j+)if (L.elemj.key < L.elemk.key) k = j;当前具最小排序码值的记录if(k!=i) 对换到第i个位置Swap ( L.elemi, L.elemk);算法分析 简单选择排序的排序码比较次数KCN与记录的 初始排列无关。设整个待排序记录序列有个记 录，则第，趟选择具有最小排序码记录所需的比 较次数总是次。总排序码比较次数为KCN = £(n i l) = i-o2 记录的移动次数与序列的初始排列有关。当这组 记录初始时已经按其排序码值从小到大有序时， 记录的移动次数RMN = O,最坏情况是每趟都要 进行交换，总记录移动次数为RMN = 3(n-1)。 简单选择排序是一种不稳定的排序方法。 简单选择排序算法只用到一个附加存储用于数据 交换。堆排序(Heap Sort) 利用堆及其运算，可以实现选择排序的思路。 堆排序分为两个步骤根据初始输入数据，利用堆的筛选算法 siftDown()形成初始堆；通过一系列的记录交换和重新调整堆进行排序。如果堆排序采用小根堆，所有记录在排序后将按 其排序码从大到小排列。所以改使用大根堆。21254925*1608初始排序码集合214908i = 2时的局部调整214908i = 1时的局部调整214908i = 0时的局部调整 形成大根堆大根堆的向下筛选算法void siftDown (dataList& H, int start, int m) int i = start; int j = 2*i+l;HElemType w = H.heapi;while (j <= m ) 藁后位置if (j < m && H.heapj.key < H.heapj+1.key )j+； 盅两子女的大者if ( w.key >= H.heapj.key ) break;else H.heapi = H.heapj; i = j; j = 2*j+l; 大子女上移，向下继续调整)H.heapi = w;回放到合适位置将表转换成堆的算法for (int i = (H.n-2) / 2 ; i >= 0; i-) siftDown( H, i, H.n-1 );基于初始堆进行堆排序 大根堆的存储结构采用完全二叉树的顺序存储， 实际上它的所有结点是保存在一维数组H.heap0 中的。对大根堆进行各种操作，实际上是对一维 数组的操作，因此，堆排序的结果将存放在一维 数组中。 大根堆排序的过程可描述如下： 大根堆堆顶H.heapO保存具有最大排序码的记 录，将H.heapO与H.heapn-1对调，把具有 最大排序码的记录交换到最后；.对前面的11-1个记录，使用堆的向下筛选算法 siftDown(H, 0, n-2),重新建立大根堆，具有次大 排序码的记录又上浮到H.heap0H立置。其中n 是堆的当前大小。 对调 H.heap0和 H.heapn-2记录，调用 siftDown(H, 0, n-3),对前n-2个记录重新筛选形 成大根堆，如此反复执行，最后得到全部排 序好的记录序列。此算法即堆排序。49252125*1608初始大根堆08 25 21 25女 16 4908252125*1649交换0号与5号记录, 5号记录就位2525*21081649从0号到4号重新 调整为大根堆16 25* 21 08 25 491625*21082549交换0号与4号记录, 4号记录就位25*1621082549从0号到3号重新 调整为大根堆08162125*254908 16 21 25* 25 49交换0号与3号记录, 3号记录就位21160825*2549从0号到2号重新 调整为大根堆08162125*254908 16 21 25* 25 49交换0号与2号记录, 2号记录就位16082125*254916 08 21 25* 25 49从0号到1号重新 调整为大根堆08162125*254908 16 21 25* 25 49交换0号与1号记录, 1号记录就位堆排序的算法void HeapSort ( maxHeap& H ) 对小根堆 H.heap0到 H.heapH.CurrentSize-l进行排序，使得表中各个记录按其排序码非递减有序。int i;for (i = (H.CurrentSize/2 -1; i >= 0; i- )siftDown ( H, i, H.CurrentSize -1); 初始堆for (i = H.CurrentSize-1; i >= 1; i- ) Swap ( H.heap0, H.heapi);/交换siftDown ( H, 0, i-1 );重建大根堆算法分析若设堆中有n个结点，且2h/WnV2h,则对应的 完全二叉树有h层。在第i层上的结点数(i = 1,2,h)。在第一个形成初始堆的for循环中 对每一个非叶结点调用了 一次堆的向下筛选算法 siftDown(),因此该循环所用的计算时间为：h-l2Z2”(h-i) i=l其中，i是层号，非叶结点最多有h-l层，第i层 最多有27个结点，第i层每个结点最多下移h-i 层。每个结点每次执行横/纵向2次比较。h-12 p i (h-i) = 2* i=lh1)*2° +(h2)*2+1*2卜2 =2* (2R2+2r3+2。)+ (2h-3+2h-4+*+2°) + + 2° h-l个=2* Qh“1) + (2h-2-l) + + (21-1)=2* (2h-x+2h-2+-+21+2°)-2°-(1+1+1) = 2*(2h-l)-l-(h-l)=2* 2h-l-h = 2*(n+l)-1-log2(n+l)l=2* n- Flog2(n+l)l当n = 255时，h =log2(n+l)1 = 8,形成初始堆得 到排序码最小记录需比较2*(255-8) = 494次。排序过程中，第i次重构堆时堆内有n-i个结点, 自顶向下筛选时,排序码比较2*Llog2(n-i)J次,n-1次重构堆的排序码比较次数为nl2*ZU°g2(ni)(2*log2(n1)+105(吁2)+ +10当1 i=l=2*log2(n-l)! -2*(n-l)log2(n-l)-1.5(n-l)=2*("l)*log2(nT)3*(n-1) 因此，堆排序的时间复杂性为O(nlog2ii)。 该算法的附加存储主要是在第二个for循环中用来 执行记录交换时所用的一个临时记录。因此该算法 的空间复杂性为0(1)。 堆排序是一个不稳定的排序方法。归并排序(Merge Sort)-归并排序采用典型的分而治之算法，描述如下：MergeSort (List) if (List的长度大于1)将序列List划分为等长的两个子序列LeftList 和Right List;MergeSort (LeftList); 对子序列递归排序MergeSort (RightList); 对子序列递归排序 将两个子序列LeftList和RightList归并为一个 序列List;两路归并(2-way merging) 归并，是将两个或两个以上的有序表合并成一个 新的有序表。 例如，原始序列L中有两个有序表L4Lm 和Lm+1L川。把它们归并成一个有序表，存 于另一序列L1的L1用L1川中。这种归并方法 称为两路归并(2-way merging)o 为了实现两路归并，需要设置3个指针：变量， 和j是表L用L.和LM+1L川的当前检测 指针。女是表L1的存放指针。leftmid mid+1 rightL | 08 21 25 25*49 62 72 93 ”16 37 54leftrightLI | 08 16 21 25 25*37 49 54 62 72 93I k 当i和j都在两个表的表长内变化时，根据对应项 的排序码的大小，依次把排序码小的记录排放到 新表女所指位置中； 当，与j中有一个已经超出表长时，将另一个表中 的剩余部分照抄到新表中。两路归并算法void merge( dataList& L, dataList& L1, int left, int mid, int right) int i = left, j = mid+1, k = left;while (i <= mid && j <= right)两两比较if ( L.elemi.key <= L.elemj.key ) Ll.elemk = L.elemi; i+; k+; else Ll.elemk = L.elemj; j+; k+;wh