天任考研小编为大家整理了“24考研计算机编程题知识点：排序--归并排序”相关内容，为报考计算机专业的考生们提供指导。更多有关计算机考研干货可关注考研备考栏目。
24考研计算机编程题知识点：排序--归并排序
归并排序(Merge Sort)法是将两个(或两个以上)有序表合并成一个新的有序表。即把待排序序列分为若干个子序列，每个子序列是有序的，然后再把这些有序子序列合并为整体有序序列。
归并操作的过程如下：
①申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。
②设定两个指针(或者数组的下标)，初位置分别为两个已经排序序列的起始位置。
③比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。
④重复步骤③，直到某一指针到达序列尾。
⑥将另一序列剩下的所有元素直接复制到合并序列尾。
归并排序的过程就是将一个待排序的序列分为若干部分，然后使用上述归井操作进行排序。可见归并排序算法的复杂度是O(nlog(n))。
问题：使用归并排序对n个整数进行升序排序。
参考代码：
int arrTmp[100]; //定义一个临时的数组
/*
*归并两个分段的结果，两个分段是数组中的[low，mid]以及[mid+1，high]中的元素
*/
void Merge(int arr[],int low, int mid, int high) {
int i=low, j=mid+1,k=high; //i、j、k分别指向待归并的两段以及临时数组
while(i<=mid && j<=high){
if(arr[i]<=arr[j]){ //此为稳定排序的关键，不能用arr[i]
arrTmp[k++]=arr[i++];
} else {
arrTmp[k++]=arr[j++];
}
}
//如果前半段没有完全被复制到临时数组中，则需要复制剩下的部分
whi1e(i<=mid){
arrTmp[k++]=arr[i++];
}
//如果后半段没有完全被复制到临时数组中，同样也需要复制剩下的部分
while(j<=high) {
arrTmp[k++]=arr[j++];
}
//写回原数组
for(i=low;i<=high;i++){
arr[i]=arrTmp[i];
}
}
/*
*归并排序算法代码:arr为待排序的数组，low为低位序号，high为高位序号
*/
void MergeSort(int arr[],int low, int high) {
if(low
int mid=(low+high)/2; //计算中间位置
MergeSort(arr, low, mid); //对数组中的前半段进行排序
MergeSort(arr, mid+1,high); //对数组中的后半段进行排序
Merge(arr,low,mid,high); //归并两个分段排序后的结果
}
}
以上是天任考研小编为大家带来的“24考研计算机编程题知识点：排序--归并排序”希望考生们都能备考顺利，考上自己心仪的院校。
