归并排序的递归实现

可定

发布于 2020-04-20 15:11:34

6420

发布于 2020-04-20 15:11:34

文章被收录于专栏：细嗅蔷薇细嗅蔷薇

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

2路归并排序的简单介绍

下面是归并排序的流程图。

可以看到，每次程序都将数字两两分组（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]);
        }
    }
}