题目描述

给定你一个长度为n的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式
输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在1~109范围内），表示整个数列。

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

数据范围
1≤n≤100000

输入样例

输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5

解析

归并思路：
1.选取中间数值
2.sort()中间数值的左右两端
3.借助一个temp变量，进行归并排序
3.将temp变量赋值给原始数组

代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int n;
int q[N], temp[N];

void merge_sort(int q[], int L, int R){
    if(L >= R) return; //边界判断

    int mid = (L + R) >> 1; // 选取中间值

    merge_sort(q, L, mid); //sort左侧数组
    merge_sort(q, mid + 1, R); //sort右侧数组

    int index1 = L, index2 = mid + 1, index3 = 0; //index1为左侧数组的游标，index2为右侧数组的游标，index3为temp数组的游标
    while(index1 <= mid && index2 <= R)
        if(q[index1] <= q[index2]) temp[index3++] = q[index1++];
        else temp[index3++] = q[index2++];

    //如果index2已经到达R的位置
    while(index1 <= mid) temp[index3++] = q[index1++];
    //如果index1已经到达mid的位置
    while(index2 <= R) temp[index3++] = q[index2++];

    //从temp数组中拷贝数据到q数组中
    for(int i = L, j = 0; i <= R; ++i, ++j) q[i] = temp[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;
}