AcWing 787. 归并排序
原题链接
简单
作者:
王一博铁粉
,
2024-02-18 21:40:26
,
所有人可见
,
阅读 28
时间复杂度 nlogn
C++ 代码
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N], tmp[N];
void merge_sort(int q[], int l, int r){
//如果区间里面的元素是一个或0个,则直接返回return。
if(l >= r) return;
int mid = l + r >> 1;
//左右两边递归排序
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int i = l, j = mid + 1, k = 0;
//左右两边合二为一
while(i <= mid && j <= r){
//为什么中间是&&呢,因为如果是||,则while会继续循环下去
//进行左右两边的数比较大小,把较小的挑出来放到tmp里面
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++];
}
//把存放在临时数组里面的数放回q数组里面
for(int i = l, k = 0; i <= r; i ++){
q[i] = tmp[k++];
}
}
//main里面只需要三个部分
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;
}
//错因:1:不应该额外加for, 2: l>=r 要提出去优先判断。