归并排序的递归实现

发布于 2020-02-20  120 次阅读


本文主要介绍2路归并排序的递归实现。

2路归并排序的简单介绍

下面是归并排序的流程图。
4237685-8247e09383de10a4.png

可以看到,每次程序都将数字两两分组(n/2个组),组内单独排序,最后将这些组两两合并,生成n/4个组,组内再单独排序。直到最后只剩下一个组为止。

2路归并排序的时间复杂度为O(logN)。

2路归并排序的递归代码实现

2路归并排序的代码递归实现特别简单,只要重复把当前区间[left,right]分为两半,对两边的子区间[left,mid]和[mid+1,right]分别进行递归,最后将两个已经有序的子区间合并为有序区间即可。

问题:

  • 怎么表达递归边界(即最后只剩下一个元素)?

if(left < right) //当各自剩下一个元素时,left=right,退出if语句

  • 拆分出来的数组元素要怎么存放?
  • 拆分出来的数组元素的下标要怎么存放?

代码如下:

#include<cstdio>
const long long maxn = 100005;
//将array数组的当前区间[left,right]进行归并排序
void mergeSort(int a[], int left, int right)
{
    if(left < right) //当各自剩下一个元素时,left=right,退出if语句
    {
        int mid = (left + right) / 2;
        mergeSort(a, left, mid);
        mergeSort(a, mid + 1, right);
        merge(a, left, mid, mid + 1, right);
    }
}
//将数组a的[l1, r1]与[l2, r2]区间合并为有序区间(l2 = r1 + 1)
void merge(int a[], int l1, int r1, int l2, int r2){
    int i = l1, j = l2;
    int temp[maxn], index = 0;  //temp临时存放合并后的数组,index为其下标
    while(i <= r1 && j <= r2){ //保证两个数组不出界到对面捣乱
        if(a[i] <= a[j]) //判断数组1的第i个元素(left)是否<=数组2的第j个元素(mid+1)(i=j)
            temp[index++] = a[i++];
        else //哪个数组的相应元素更小就先加入,并统计归并后的数组元素个数(index)
            temp[index++] = a[j++];
    }
    while(i <= r1) temp[index++] = a[i++]; //将[l1,r1]的剩余元素加入序列temp
    while(j <= r2) temp[index++] = a[j++]; //将[l2,r2]的剩余元素加入序列temp
    for(i = 0; i < index; i++){
        a[l1 + i] = temp[i]; //
    }
}
int main(){
    int n; // 组数

    while(scanf("%d", &n) != EOF, n--){
        long long m; // 待排序数字的个数
        scanf("%lld", &m);
        int a[maxn];
        for(int i = 0; i < m; i++){
            scanf("%d", &a[i]);
        }
        mergeSort(a, 0, m - 1);
        for(int i = 0; i < m; i++){
            printf("%d\n", a[i]);
        }
    }
}

其中的merge是由two points的文章改编而来(挖坑,待解决)。

参考

算法笔记3105ProblemB 基础排序III:归并排序

本文标题:《归并排序的递归实现》

本文链接:https://wnag.com.cn/898.html

特别声明:除特别标注,本站文章均为原创,本站文章原则上禁止转载,如确实要转载,请电联:wangyeuuu@qq.com,尊重他人劳动成果,谢过~


正因为有要好好实现的梦想,所以今天也要好好加油。