归并排序 拓展1：使用线性表完成。 #define MAXSIZE 100 /*线性表中最大元素个数*/ typedef int KeyType; /*关键字类型*/ typedef struct{ KeyType Key; /*关键字域*/ }LineList; /*线性表元素类型*/(用c语言写。)

归并排序是一种高效的排序方法，采用分治法的策略将已有序的子序列合并，从而得到完全有序的序列。其核心思想是把待排序数组分成若干个小数组，每个小数组内部有序，然后逐步两两合并成更大的有序数组。 下面是使用线性表结构实现的归并排序代码示例： ```c #include <stdio.h> #define MAXSIZE 100 typedef int KeyType; typedef struct{ KeyType Key; }LineList; void MSort(LineList R[], LineList TmpR[], int low, int high);/*递归划分*/ void Merge(LineList R[], LineList TmpR[], int low, int mid, int high); //主函数调用 void MergeSort(LineList R[]){ LineList *TmpR = (LineList*)malloc(sizeof(LineList)*MAXSIZE); if(TmpR != NULL){ MSort(R,TmpR,0,MAXSIZE-1); free(TmpR); } } void MSort(LineList R[], LineList TmpR[], int low, int high){ int mid; if(low<high){/*当low>=high时，说明该区间内只有一个元素，无需再分割*/ mid=(low+high)/2;/*找中间位置进行划分*/ MSort(R,TmpR,low,mid);/*左半部分继续递归划分*/ MSort(R,TmpR,mid+1,high);/*右半部分继续递归划分*/ Merge(R,TmpR,low,mid,high);/*左右两个子区间的元素已经排好序，现在需要将其合并到一起形成更大范围内的顺序排列*/ } } void Merge(LineList R[], LineList TmpR[], int low, int mid, int high){ int i=low,j=mid+1,k=low; while(i<=mid && j<=high){ if(R[i].Key <= R[j].Key) /*比较两边的数据大小并将较小者放入临时存储区域*/ TmpR[k++] = R[i++]; else TmpR[k++] = R[j++]; } while(i<=mid) /*如果左边还有剩余，则全部复制过去*/ TmpR[k++]=R[i++]; while(j<=high)/*同理右边如果有剩下的也一样处理*/ TmpR[k++]=R[j++]; for(k=low;k<=high;k++) /*最后从暂存空间拷贝回原数组对应位置上覆盖原有数据即可完成一次局部调整操作过程*/ R[k]=TmpR[k]; } ``` 此段程序实现了简单的归并排序功能。其中`Merge()`负责实际的合并工作；而`MSort()`则通过递归来不断细分输入直到每一分块都足够简单可以直接求解为止然后再逐层返回依次构造最终解答方案的过程。