3.Acwing基础课第787题-简单-归并排序
3.Acwing基础课第787题-简单-归并排序题目描述
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例
5
3 1 2 4 5输出样例
1 2 3 4 5思路解析：
算法：归并排序 （ Quick Sort ）
时间复杂度：O(nlog(n))
解题思路：
归并排序是一种分治算法。它将一个大的数组不断分成两个子数组，递归地对两个子数组进行排序，然后再将排好序的子数组合并起来。
代码：
#include using namespace std;const int N = 10e6 + 10;int n;int q,tmp;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
页:
[1]