3.Acwing基础课第787题-简单-归并排序

3.Acwing基础课第787题-简单-归并排序

题目描述

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

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

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

1≤n≤100000
输入样例

1. 5
2. 3 1 2 4 5

复制代码

输出样例

1. 1 2 3 4 5

复制代码

思路解析：

算法：归并排序 （ Quick Sort ）

时间复杂度：O(nlog(n))

解题思路：

归并排序是一种分治算法。它将一个大的数组不断分成两个子数组，递归地对两个子数组进行排序，然后再将排好序的子数组合并起来。

代码：

[code]#include using namespace std;const int N = 10e6 + 10;int n;int q[N],tmp[N];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