首页 25考研 在职考研 0元畅学 26考研

新东方在线 > 考研 > 计算机 > 考研计算机复习指导 > 正文

扫码加入训练营

牢记核心词

学习得礼盒

2023考研计算机编程题知识点之排序--归并排序

2022-11-21 07:56:00来源：网络

　　今天新东方在线考研频道小编为各位考生整理了“2023考研计算机编程题知识点之排序--归并排序”，相关内容。专业、实用的计算机考研复习备考内容，能使大家更有效率的掌握相关知识点，避免盲目学!更多计算机考研复习精彩内容，时刻关注新东方在线考研频道!

　　2023考研计算机编程题知识点之排序--归并排序

　　归并排序(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); //归并两个分段排序后的结果

　　}

　　}

　　以上就是关于“2023考研计算机编程题知识点之排序--归并排序”的内容，更多计算机考研复习精彩内容，请持续关注新东方在线考研频道!


本文关键字: 考研计算机 计算机考研复习

考研英语核心词汇营

背词+听课+练习+督学，学习得礼盒

更多资料

添加班主任领资料

添加考研班主任
免费领取考研历年真题等复习干货资料

  • 1.打开手机微信【扫一扫】，识别上方二维码；
  • 2.添加班主任，可领取学习资料。
更多>>
更多内容
25考研 在职研 AI择校 去测评 领资料

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】，识别上方二维码；
2.点击【关注公众号】，获取资料大礼包。

考研资料大礼包

历年考研真题及答案解析下载

英语一 英语二 政治 数学一 数学二 数学三 西医综合 教育综合 心理学综合
立即下载
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
我要
反馈 返回
首页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10