天任考研小编为大家整理了“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考研计算机编程题知识点：排序--归并排序”希望考生们都能备考顺利，考上自己心仪的院校。