题目描述

给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1≤n≤100000

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

算法模板：

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

思路图示：

https://visualgo.net/zh/sorting

思路口诀：

一判二定三递归，四合五分支六复制

算法1：C++版

#include <iostream>
using namespace std;

int n;
const int N=1000010;
int q[N];
int tmp[N];

void merge_sort(int q[],int l,int r){
    if(l>=r)return;//1:判空
    int mid=l+r>>1;
    //2:递归排序左边、右边
    merge_sort(q,l,mid),merge_sort(q,mid+1,r);
    //3:开始合并
    int i=l,j=mid+1,k=0;//k表示当前tmp数组已合并数的数量

    while(i<=mid&&j<=r){
        if(q[i]<=q[j])
            tmp[k++]=q[i++];
        else
            tmp[k++]=q[j++];
    }
    //4：只剩其中一个数组后判断
    while(i<=mid){
        tmp[k++]=q[i++];
    }
    while(j<=r){
        tmp[k++]=q[j++];
    }
    //将临时数组tmp内容复制到原数组q
    for(i=l,j=0;i<=r;i++,j++)
        q[i]=tmp[j];

}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&q[i]);
    }
    merge_sort(q,0,n-1);
    for(int i=0;i<n;i++){
        printf("%d ",q[i]);
    }
    return 0;
}

算法2：Java版

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 * Created by Yolanda on 2021/4/26 10:43
 */
public class Main {

    static void merge_sort(int[] q,int l,int r)
    {
        if(l>=r) return;
        int mid=l+r>>1;
        int k=0,i=l,j=mid+1;
        int[] tmp = new int[r-l+1];//注意：q.length会超时，总结：一般用函数都会超时
        merge_sort(q,l,mid);
        merge_sort(q,mid+1,r);
        while(i<=mid&&j<=r){
            if(q[i]<=q[j]) tmp[k++]=q[i++];
            else tmp[k++]=q[j++];
        }
        while (i<=mid) tmp[k++]=q[i++];
        while (j<=r) tmp[k++]=q[j++];

        //数组的复制：
        for (i=l,j=0; i<=r ; i++,j++) {
            q[i]=tmp[j];
        }
//        System.arraycopy(tmp,0,q,l,j); //尚不可用，原因未知
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        String[] a=br.readLine().split(" ");
        int[] b=new int[n];
        for (int i = 0; i < n; i++) {
            b[i]=Integer.parseInt(a[i]);
        }
        merge_sort(b,0,n-1);

//        System.out.println(Arrays.toString(b));
        for (int i = 0; i < n; i++) {
            System.out.print(b[i]+" ");
        }
    }
}