Loading... # 排序 ## 基本概念 * 排序码：是结点中的一个或多个字段，其值作为排序运算中的依据。排序码可以是关键码也可以不是关键码(结果不唯一)。 * 记录与文件：在排序中将结点称为记录，将一系列结点构成的线性表称为文件。 * 排序（sorting）又称分类。假定具有n个记录$\lbrace A_1，A_2，...，A_n\rbrace $的文件，每个记录有一个排序码 $k_i$，$\lbrace K_1，K_2，...，K_n \rbrace $是相应的排序码的集合。排序运算就是将上述文件中的记录按排序码非递减（或非递增）的次序排列成有序序列。 * 内排序与外排序：在排序过程中，文件全部放在内存处理的排序算法称为"内排序"；在排序过程中，不仅需要使用内存，而且还要使用外存的排序算法称为"外排序"。 * 按照所采用的策略分类：插入排序、选择排序、交换排序、分配排序、归并排序。 * 稳定与不稳定：如果一个排序算法对于任意具有相同排序码的多个记录在排序之后。这些具有相同排序码的记录的相对次序仍然保持不变，则称该排序算法为"稳定的"；否则称该排序算法是"不稳定的"。 * 指标： 1. 算法执行时所需的时间： 是衡量一个排序算法好坏的最重要的性能指标。排序算法的时间开销通常用算法执行中的**1. 比较次数**和**2. 记录移动次数**表示。衡量这些排序算法的性能可以采用最大执行时间和平均执行时间。 2. 算法执行时所需的内存空间 ## 插入排序 每次选择待排序的记录序列的第1个记录，按照排序码的大小将其插入已排序的记录序列中的适当位置，直到所有记录全部排序完毕。 ### 直接插入排序 先将第1个记录视为一个有序的记录序列，然后从第2个记录开始，依次将未排序的记录插入这个有序的记录序列中，直到整个文件中的全部记录排序完毕。在排序过程中，前面的记录序列是已经排好序的，而后面的记录序列有待排序处理。 sort.h ```c typedef int ElemenType; struct forSort { ElementType key; }; typedef struct forSort Forsort; void InitForSort(ForSort *FS, int a) { FS->key=a; } ``` sort.c ```c void DirectInsertionsSort(ForSort A[], int n) { int i,j; ForSort temp; for(i=1;i<n;i++) { j=i; temp=A[i]; while(j>0&&temp.key<A[j-1].key) { A[j]=A[j-1]; j--; } A[j]=temp; } } ``` 此插入算法不需要交换(比较时交换)。平均比较次数为：$1/2+2/2+ \cdots +(n-1)/2=n(n-1)/4$时间复杂性为$O(n^2)$。直接插入排序是稳定的。 ### 折半插入排序 将直接插入排序中寻找A[i]插入位置的方法改为采用折半比较。前提是文件必需按顺序存储。 ```c void BinaryInsertionSort(ForSort A[],int n) { int i,k,r; ForSort temp; for(i=1,i<n;i++) { temp=A[i]; k=0; r=i-1; while(k<=r) { int m; m=(k+r)/2; /*即使k=r也会继续比，此时小于r会减1，k即是插入的位置，大于或等于k会加一，k还是插入的位置。*/ if(temp.key< A[m].key)/*这个条件保证后来的相同排序码会排在后面*/ r=m-1/*在前半部分继续寻找插入位置*/ else k=m+1/*在后半部分继续寻找插入位置*/ } /*找到插入的位置，先将A[k]~A[k-1]右移一个位置*/ for(r=i;r>k;r--) A[r]=A[r-1]; A[k]=temp; } } ``` 采用k>r来控制折半的结束，此时k就是应该插入的位置。折半插入排序是稳定的。 假设$n=2^k$，当$2^j \lt i \lt 2^{j+1}$，需要的比较次数为j+1。因此，总的比较次数为： $$ (1式)：\begin{equation}\begin{split} \sum_{i=1}^{n}\lceil log_2i\rceil &=\sum_{i=1}^{k}\sum_{j=i}^k2^{j-1} \\ &=\sum_{i=1}^{k}(2^k-2^{k-1}) \\ &=k \times 2^k-2^k+1 \\ &=n\times log_2n +1 \\ & \approx n\times log_2n \end{split}\end{equation} $$ 时间复杂度为$O(nlog_2n)$记录移动次数与算法DirectInsertoinsSort相同。 ### Shell排序 Shell排序法又称希尔排序法、缩小增量排序法。Shell 排序的基本思想是：先选定一个整数$s_1 < n$，把待排序文件中的所有记录分成$s_1$个组，所有距离为$s_1$的记录分在同一组内，并对每一组内的记录进行排序。然后，取 $s_2< s_1$，重复上述分组和排序的工作。当到达 $s_i=1$ 时，所有记录在同一个组内排好序。 各组内的排序通常采用直接插入法。由于开始时s的取值较大，每组内记录数较少，所以排序比较快。随着$s_i$的不断缩小，每组内的记录数逐步增多，但由于已经按$s_{i-1}$排好序，因此排序速度也比较快。 例：  ```c void ShellSort(ForSort A[],int n, int s) { int i,j,k; ForSort temp; { for(k=s;k>0;k>>=1) { for(i=k;i<n;i++)/*分组排序*/ { temp=A[i] j=i-k; while(j>=0&&temp.key<A[j].key) { A[j+k]=A[j]; j-=k; } A[j+k]=temp; } } } } ``` shell排序不稳定，在此不对Shell排序的速度分析。 ## 选择排序 选择排序的基本思想是：每次从待排序的记录中选出排序码最小的记录，再在剩下的记录中选出次最小的记录，重复这个过程，直到完成全部排序。 ### 直接选择排序 每次从待排序的记录中选出排序码最小的记录，顺序放在已排序记录序列的最后，直到完成全部排序。 ```c void DirectSelectSort(ForSort A[], int n) { int i,j,k; ForSort temp; for(i=0;i<n-1;i++) { k=i; for(j=i+1;j<n;j++) if(A[j].key<A[k].key) k=j; if(i!=k) { temp=A[k]; A[k]=A[i]; A[i]=temp; } } } ``` 比较次数为：$\sum_{i=1}^{n-1}= \frac {n(n-1)} 2$。移动次数最少为0，最多为3(n-1)(倒序)。 ### 树形选择排序 树形选择排序又称为竞赛树排序或胜者树。基本思想∶ 把n个排序码两两进行比较，取出$\lceil \frac n 2\rceil $个较小的排序码作为第一步比较的结果保存下来，再把$\lceil \frac n 2\rceil $个排序码两两进行比较，重复上述过程，一直比较出最小的排序码为止。这期间要比较n-1次，再把这个最小的数的位置用$\infty$替代，再次进行上述过程，因为其它位置的记录并未改变，所以只要重新比较原最小数所在的路即可。  总比较次数为$(n-1)+(n-1)log_2n\approx nlog_2n $移动次数不超过比较次数，总时间开销为$O(nlog_2n)$ ## 交换排序 交换排序的基本思想是∶每次将待排序文件中的两个记录的排序码进行比较，如果不满足排序要求，则交换这两不记录在文件中的顺序，直到文件中任意两个记录之间都满足排序要求为止。 ### 起泡排序 起泡排序是最简单的交换排序。起泡排序的排序过程如下∶首先比较第1个记录和第 2个记录的排序码，如果不满足排序要求，则交换第1个记录和第2个记录的位置;然后对第2个记录（可能是新交换过来的最初的第1个记录）和第3个记录进行同样的处理;重复此过程，直到处理完第n-1个记录和第n个记录为止。上述过程称为一次起泡过程，这个过程的处理结果就是将排序码最大（非递减序）或最小（非递增序）的那个记录交换到最后一个记录位置，到达这个记录在最后排序后的正确位置。然后，重复上述起泡过程，但每次只对前面的未排好序的记录进行处理，直到所有的记录均排好序为止。 在每次起泡过程中，可以设立一个标志位，用以标示每次起泡过程中是否进行过记录交换。如果某次起泡过程中未发生交换，则表明整个记录已经达到了排序要求。显然，对n个记录的排序处理最多需要 n-1次起泡过程。  ```c void BubbleSort(Forsort A[], int n) { int i,j; Bool Flag; ForSort temp; for(i=n-1,flag=(Bool)1;i>0&&flag;i--) { falg=FALSE; for(j=0;j<i;j++) if(A[j+1].key<A[j].key) { falg=TRUE; temp=A[j+1]; A[j+1]=A[j]; A[j]=temp; } } } ``` 比较前如果已经是顺序则比较次数为n-1，移动次数为0次；如果是逆序则需要进行n-1次排序，此时比较次数为最大：$\sum_{i=1}^{n-1} i = \frac{n(n-1)}2 $每次比较要进行交换，每次交换要进行3次移动，移动次数为： $3\sum_{i=1}^{n-1} =\frac {3n(n-1)} 2$ 显然起泡排序是稳定的。 ### 快速排序 快速排序算法又称分区交换排序算法，该排序算法使用分割法对排序文件中的记录进行排序。快速排序算法的排序处理过程如下∶从待排序记录中任选一个记录，以这个记录的排序码作为中心值，将其他所有记录划分成两个部分，第1部分包括所有排序码小于等于中心值的记录，第 2部分包括所有排序码大于中心值的记录，而其排序码作为中心值的这个记录，在排序后必然处在这两部分的中间位置;对上述两部分继续采用同样的方式进行排序处理，直到每个部分为空或者只含有一个记录为止。至此，待排序文件中的每个记录都被放置到正确的排序位置。 **看图就会懂**，看不懂再看文字  例： 例 5-7 设某文件中待排序记录的排序码分别为28、13、72、85、39、41、6、20。用快速排序法对该文件进行排序，第 1 趟排序过程如下∶ 取第1个记录的排序码 28为中心值，排序过程采用从两边向中间夹入的方法进行分组处理。首先，取出第1个记录，将第1个记录的位置空出，将中心值28与最后一个（第8个）记录的排序码20进行比较，因为28大于20，故将第8个记录交换到空出的第1个记录位置。这样，当前空出的记录位置为第8个记录位置，比较改为在前端进行，即将中心值28与第2个记录的排序码13进行比较，因28大于13，故第2个记录保持不变;继续比较中心值28和第3个记录的排序码72，因28 小于72，故将第3个记录交换到当前空出的第8个记录位置。此时，空出的记录位置是第3个记录位置，比较改为在后端进行，即将中心值28与第7个记录的排序码6进行比较，因28大于6，故将第7个记录交换到当前空出的第3个记录位置。此时，空出的记录位置是第7个记录位置，比较又改为在前端进行，即将中心值28与第4个记录的排序码85进行比较，因28 小于85，，故将第4个记录交换到当前空出的第7个记录位置。此时，空出的记录位置是第4个记录位置，比较改为在后端进行，即将中心值28与第6个记录的排序码 41进行比较，因 28小于41，故第6个记录保持不变;继续比较中心值28和第5个记录的排序码39，因28小于39，故第5 个记录也保持不变。此时，所有记录均比较完毕，将中心值28所对应的记录排序到正确的位置，即当前空出的第 4个记录位置。所有记录比较完毕，当前空出的记录位置是第4个记录，故将取出的中心放在第4个记录位置，该记录已正确排好序。第1 趟排序处理后的结果为∶ 20 13 6 **28** 39 41 85 72 中心值将其他所有记录划分成两部分，第1部分是中心值记录前端的部分，包括3个记录，其排序码均小于等于中心值;第2部分是中心值记录后端的部分，包括4个记录，其排序码均大于中心值。 对上述两部分采用同样方法进行处理，直到所有记录排好序。可以看出，快速排序是一个递归算法。 ```c void QuickSort(ForSort A[],int low,int high) { int i,j; ForSort temp; if(low>=high) return; i=low; j=high; temp=A[i]; while(i<j) { while(i<j&&temp.key<A[j].key) j--;/*在右边比较，比中心值大的就不动了*/ if(i<j)/*i<j判定有没有比较完*/ A[i++]=A[j];/*移位同时相当于A[j]空出来了(因为A[i]和A[j]互换了，A[i]本来的值temp是相当于空出来的)*/ while(i<j&&A[i].key<=temp.key) i++;/*在左边比较，比中心值小的就不动了*/ if(i<j) A[j--]=A[i];/*同上，A[j]又空出来了temp值到到A[j]上*/ } A[i]=temp; QuickSort(A,low,--j);/*递归处理排序码小于等于中心值的那组记录*/ QuickSort(A,++i,high);/*递归处理排序码大于等于中心值的那组记录*/ } ``` **快速排序时间复杂度分析** 快速排序最好的情况是，每次选取的中心值记录恰好将其他记录分成大小相等（最多相差一个记录）的两部分。第1遍扫描时，经过大约n次（实际为n-1次）比较，产生2个大小约为n/2的子文件。第2遍扫描时，对每个子文件经过大约n/2次比较，产生4个大小约为n/4的子文件，这一阶段总的比较次数约为2（n/2）次。第3遍扫描时，处理4个大小约为n/4 的子文件，需要大约4（n/4）次比较。依此类推，在经过k=logzn遍扫描后，所得到的子文件大小为1，算法终止，排序结束。因此，总的比较次数约为∶ $1(n/1)＋2(n/2)+4(n/4)+…+2(n/n)=n＋n+…+n=nk=nlog_2n$ 最坏的情况下，所选取的中心值总是最大或最小的排序码，当待排序文件中的记录已经符合排序要求的记录顺序时就是如此。第1遍扫描时，经过n-1次比较;得到一个大小为n一1的子文件。第2遍扫描时，经过n-2次比较，得到一个大小为n-2的子文件。依次类推，第n-1遍扫描时，得到一个大小为1的子文件，算法终止。因此，总的比较次数为∶ $$ (2式)：\begin{equation}(n-1)+(n-2)+…+1=n(n-1)/2\end{equation}$$ 总体而言，可以证明快速排序算法的平均时间复杂性为$O(nlog_2n)$，下面给出证明 过程。 设T(n)代表对长度为n的文件进行快速排序的平均时间开销，显然进行一趟快速排序的时间与文件的长度n成正比，设为c、n，不难得到$T(n)= T(i)+T(n-1-i)+ cn$ 设快速排序将待排序的文件分成长度为$(0,n-1),(1,n-2),\cdots ,(n-1,0)$的两个子文件的概率相同。设为1/n 则 $$(3式)：\begin{split} \frac{T(i)+T(n-1-i)}{2} &=\frac 1n\sum_{k=0}^{n-1}\frac {(T(k)+T(n-1-k)) }{2} \\ &=\frac 1n \sum_{k=0}^{n-1}T(k) \end{split} $$ 将(3)代入(2)式得 $$ (4式)：T(n)=cn+\frac n2\sum_{k=0}^{n-1}T(k) $$ 故： $$ (5式)：nT(n)=cn^2+n\sum_{k=0}^{n-1}T(k) $$ 以n-1替代n $$ (6式)：(n-1)T(n-1)=c(n-1)^2+2\sum_{k=0}^{n-2}T(k) $$ (5式)减(6式)得 $$ (7式)：nT(n)-(n-1)T(n-1)=c(2n-1)+2T(n-1) $$ $$ (8式)：nT(n)=(n+1)T(n-1)+2cn-c $$ 忽略常数c，改写为 $$ (9式)：\frac{T(n)}{n+1}=\frac{T(n-1)}n+\frac{2c}{n+1} $$ 递推得 $$ (10式)：\frac{T(n)}{n+1}=\frac{T(1)}2+2c\sum_{i=1}^{n+1}\frac1i=ln(n+1)+\gamma-\frac32=O(log_2n) $$ 此处$\gamma\approx0.577$为欧拉常数 由此可见，快速排序算法平均时间复杂性为$O(nlog_2n)$平均需要$O(log_2n)$趟快速排序过程，平均空间开销为$O(log_2n)$ 快速排序算法是不稳定的。 ## 分配排序 ### 基本思想 **可以不看** 为了帮助理解分配排序的基本思想，先看一个具体问题。有一堆卡片，记载了从1981年1月1日到2000年12月30日之间每天的工作摘要;每张卡片上标明了日期（年、月、日），并记载了当日的工作内容摘要。现在的问题是，为了查找卡片方便，需要对这堆卡片进行排序，按年月日的先后顺序将这些卡片有序地存放起来，这样，当需要了解某一天的工作概况时，可以非常方便地查找到所需要的卡片。 解决这个问题有两种具体方法。第1种方法是，先将所有卡片按年份分成大组，第1大组中是1981年的卡片，第2大组中是1982年的卡片，最后一个大组中是2000年的卡片;然后对分在同一大组中的所有卡片按月份分成小组，每一大组中的第1小组是1月份的卡片，第2小组是2月份的卡片，第12小组是12月份的卡片；再对每一小组中的卡片按日期由小到大的顺序进行排序；最后，将所有排序后的各组卡片依次收集起来，最上面的是第1大组中第1小组的卡片，紧接着是第1大组中第2小组的卡片，依次类推，最下面的卡片是最后一个大组中的第 12 组卡片。第2种方法是，先将所有卡片按日期分成31个组，第1组中是日期为1号的卡片，第2组中是日期为2号的卡片，第31组是日期为31号的卡片，然后将所有卡片依次收集起来，第1组在最上面，第31组在最下面；对收集起来的全部卡片，再按月份依次分到12个组内，每组内的卡片保持在本次收集起来后未分组前的相对先后关系，第1组是1月份的卡片，第2组是2月份的卡片，最后一组是12月份的卡片，然后又将所有卡片依次收集起来，第1组在最上面，第12组在最下面；最后，再将所有卡片按年份分到20个组，同样地，每组内的卡片保持在本次收集起来后未分组前的相对先后关系，第1组是1981年的卡片，第2组是1982年的卡片，第20组是2000年的卡片，然后再将所有卡片收集起来，第1组在最上面，紧接着是第2小组的卡片，最下面是第 20 组卡片。 显然，这两种方法都涉及一个先分配后收集的过程。所不同的是，第1种方法是从处在最高位的年份开始进行分配，称为"最高位优先（Most Significant Digit First）分配法";第2种方法是从处在最低位的日期开始进行分配，称为"最低位优先（Least Significant Digit First）分配法"。采用"最高位优先分配法"时，先分成大组，然后对每一大组进行再分组，依此类推，最后经过一次收集即可。显然，不断分组的过程是一个递归的过程。因此.通常采用"最低位优先分配法"。 从上述对卡片排序的过程可以看出，当排序码是多个字段的组合时，采用分配排序是一种非常自然的排序方法。但是，分配排序也可以用于解决由单个字段构成的简单的排序码情况，这就是下面要讨论的基数排序。 ### 基数排序 基数排序的基本思想是把每个排序码看成是一个d元组：$K_i=(K_i^0,K_i^1,\cdots,K_i^{d-1})$其中每个$K-i$有r种可能的取值：$c_0,c_i,\cdots,c_{i-1}$基数r的选择和排序码的类型有关，当排序码是二进制数时，最自然的取值是$r=10,c_0=0,c_1=1,\cdots,c_{r-1}=9$，d为排序码的最大位数。当排序码是大写英文字符串时，$r=10,c_0='A',c_1='B',\cdots,c_{r-1}='Z'$d为排序码字符串的最大长度。排序时，先按最低位$K_i^{d-1}$的值从小到大将待排序的记录分配到r个盒子中，然后依次收集这些记录，再按$K_i^{d-2}$的值从小到大将全部记录重新分配到r个盒字中，并注意保持每个盒子中记录之间在分配前的相对先后关系，再重新收集起来……如此反复，直到对最高位$K_i^0$分配后，收集起来的序列就是排序后的有序序列，至此，基数排序完成。 执行基数排序算法时，可采用顺序存储结构，用一个数组存放待排序的n个记录，用r个数组存放分配时所需的r个队列，每个队列最大需要n个记录的空间。每分配二次，需要移动n个记录，收集一次也需要移动n个记录，这样，d 趟分配和收集共需移动 2dn 个记录，且需要rn个附加空间，显然代价很高。 如果采用链式存储结构，将移动记录改为修改指针，则可克服顺序存储所存在的空间和时间耗费问题，示例中给出的便是采用链式存储结构。 下面给出基数排序的函数RadixSort，该函数的参数是指向被排序文件的单链表的指针pData（包含头结点）、组成排序码的基数的下界Clow 和上界 Chigh、排序码的最大长度d。 ```c struct forSort { int key[3]; struct froSort *next; }; typedef struct forSort ForSort; void RaidxSort(ForSort *pData,int Clow,int Chight,intd) { typedef struct { ForSort *Head ForSort *pTail; }Templink; int r=Chigh-Clow+1,i,j,k; Templink *tlink; ForSort *p; tlink=(TempLink*)malloc(sizeof(TempLink)*r); for(i=d-1;i>=0;i--) { /*初始化r个分配队列*/ for(j=0;j<r;j++) tlink[j].pHead=tlink.pTail=NULL; /*将记录的排序码分配到r个队列中*/ for(p=pData;p!=NULL;p=p->next) { j=p->key[i]-Clow; if(tlink[j].pHead==NULL) tlink[j].pHead=tlink[j].pTail=p; else { tlink[j].pTail->next=p; tlink[j].pTail=p; } } /*收集r个队列中的排序码*/ j=0; while(tlink[j].pHead==NULL) j++; pData=tlink[j].pHead; p=tlink[j].pTail; for(k=j+1;k<r;k++) if(tlink[k].pHead!=NULL) { p->next=tlink[k].pHead; p=tlink[k].pTail; } p->next=NULL; } /*输出排序结果*/ for(p=pData;p!=NULL;p=p->next) { for(i=0;i<d;i++) printf("%d",p->key[i]); printf(", "); } free(tlink); printf("\n") } ``` 基数排序的算法复杂性取决一直在基数和排序码的长度，每执行一次分配和收集，队列初始化需要O(r)的时间，收集工作需要O(r)的时间，即每一趟都需要O(n+2r)的时间，总共执行d趟，共需要O[d(n+2r)]的时间，排序过程中不涉及记录的移动。需要的附加存储空间包括每个记录增加一个指针共需要O(n)的空间，以及需要一个分配队列占用O(r)的空间，总的附加空间为O(n+r) 基数排序适合记录较多、排序码分布比较均匀(d较小的情况)特别是排序过程中不需要移动记录，因而当记录的数据信息较大时执行效率很高。 基数排序算法是稳定的。 ## 归并排序 当待排序的文件已经是部分排序时，可以采用将已排序的部分进行合并的方法，将部分排序的记录归并成一个完全有序的文件，这就是将要讨论的归并排序。所谓部分排序，是指一个文件划分成若干个子文件，，整个文件是未排序的，但每个子文件内是已经排序的。 归并排序的基本思想∶将已经排序的子文件进行合并，得到完全排序的文件。合并时只要比较各子文件的第 1个记录的排序码，排序码最小的那个记录就是排序后的第1个记录，取出这个记录，然后继续比较各子文件的第1个记录，便可找出排序后的第2个记录。如此反复，对每个子文件经过一趟扫描，便可得到最终的排序结果。 对于任意的待排序文件，可以把每个记录看做是一个子文件，显然这样的子文件是已经部分排序的，因而可以采用归并排序进行排序。但是，要想经过一趟扫描将 n个子文件全部归并显然是困难的。通常，可以采用两两归并的方法，即每次将两个子文件归并成一个大的子文件。第1趟归并后，得到$\frac n2$个长度为2的子文件；第 2 趟归并后，得到$\frac n4 $个长 度为4的子文件。如此反复，直到最后将两个长度为$\frac n2$的记录经过一趟归并，即可完成对文件的排序。 上述归并过程中，每次都是将两个子文件归并成一个较大的子文件，这种归并方法称为"二路归并排序"，此外，也可以采用"三路归并排序"或"多路归并排序"。通常采用"二路归并排序"方法。 ```c #include <memory.h> typedef int ElementType; struct forSort { ElementType key; }; void InitForSort(ForSort *FS, int a){ FS->key=a; } typedef struct forSort ForSort; void TwoWayMerge(ForSort Dst[], ForSort Src[],int s,int e1, int e2); void OnePassMerge(ForSort Dst[],ForSort Src[],int Len,int n); void Mergesort(ForSort A[],int n) { int k; ForSort *B=(ForSort *)malloc(n*sizeof(ForSort)); k =1; while(k<n) { /*将A中的子文件经过一趟归并归并到数组B*/ OnePassMerge(B,A,k,n); k<<=1; if(k>=n) /*已归并并排序完毕，但结果在临时数组B中，调用标准函数memcpy()将其复制到A中。memcpy()包含在头文件<memory.h>或<string.h>*/ memcpy(A,B,n*sizeof(ForSort)); else{ OnePassMerge(A,B,k,n); } } } void OnePassMerge(ForSort Dst[],ForSort Src[],int Len,int n) { int i; for(i=0;i<n-2*Len;i+=2*Len) /*执行两两归并，将Src中长度为Len的子文件归并成长度为2*Len的子文件，结果存放在Dst中*/ TwoWayMerge(Dst,Src,i,i+Len-1,i+2*Len-1); if(i<n-Len) /*尾部至多还有两个子文件*/ TwoWayMerge(Dst,Src,i,i+Len-1,n-1); else /*尾部可能还有一个子文件，直接复制到Dst中*/ mempcy(&Dst[i],&Src[i],(n-i)*sizeof(ForSort)); } void TwoWayMerge(ForSort Dst[], ForSort Src[],int s,int e1, int e2) { int s1,s2; for(s1=s,s2=e1+1;s1<=e1&&s2<=e2;) if(Src[s1].key<=Src[s2].key) Dst[s++]=Src[s1++]; else Dst[s++]=Src[s2++]; if(s1<=e1)/*第1个子文件未归并完，将其直接复制到Dst中*/ memcpy(&Dst[s],&Src[s1],(e1-s1+1)*sizeof(ForSort)); else/*第二个子文件未归并完，将其复制到Dst中*/ memcpy(&Dst[s],&Src[s2],(e2-s2+1)*sizeof(ForSort)); } ``` ## 外部排序 前面已经研究了内排序的方法。若待排序的文件很大，就无法将整个文件的所有记录同时调入内存进行排序，只能将文件存放在外存上，称这种排序为外部排序。外部排序的过程，主要是依靠数据的内外存交换和"丙部归并"两者的结合实现的。首先，按可用内存大小，将外存上含有n个记录的文件分成若干长度为t的子文件（或段）；其次，利用内部排序的方法，对每个子文件的t个记录进行内部排序。这些经过排序的子文件（段）通常称为顺串（run），当顺串生成后即将其写入外存。这样，在外存上就得到了$4m(m= \lceil n/t \rceil )$个顺串。最后，对这些顺串进行归并，使顺串的长度逐渐增大，直至所有得排序的记录成为-个顺串为止。本节主要研究对顺串进行归并的方法。 ### 外部排序自己看书 lit}$$ Last modification：January 20, 2023 © Allow specification reprint Like 如果觉得我的文章对你有用，请留下评论。