原题链接
https://www.acwing.com/problem/content/description/789/
2021/4/19 21:10
思路
- 先分开,分成俩个组
- 用双指针遍历,小的放入tmp数组
- 如果有剩余,把剩余放入tmp数组
- 把tmp的数据替换到q数组中
后续会更新
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| #include <iostream>
using namespace std;
const int N = 1000010;
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; // k表示,tmp当前放入的第几个数
while(i <= mid&&j <= r) // 俩组数据比较大小,双指针算法,小的放入tmp if(q[i] <= q[j]) tmp[k ++ ]=q[ i ++]; else tmp[k ++] = q[j ++];
while(i <= mid) tmp[k ++] = q[i ++]; //把剩余的数据放进tmp,从tmp[k]开始放 while(j <= r) tmp[k ++] = q[j ++];
for(int i=l,j=0;i<=r;i++,j++) q[i]=tmp[j]; //把q的数据换成tmp的数据
} 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; }
|