归并排序
2023-08-15 14:37:04
发布于：河北
3阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N];
// 归并思想： 俩有序，可以用归并思想合并
void merge_sort(int l, int r){
if(l >= r) return;
int mid = l + r >> 1;
// 归：递归 (函数作用是使数组有序)
merge_sort(l, mid);
merge_sort(mid+1, r);
//合并：两个有序的数列
int i = l, j = mid+1;
int idx = l;
while(i <= mid && j <= r){
if(a[i] < a[j]){
b[idx++] = a[i++];
}else{
b[idx++] = a[j++];
}
}
while(i <= mid) b[idx++] = a[i++];
while(j <= r) b[idx++] = a[j++];
// 还原a
for(int i=l; i<=r; i++){
a[i] = b[i];
}
}
int main(){
int n; cin>>n;
for(int i=0; i<n; i++){
cin>>a[i];
}
merge_sort(0, n-1);
for(int i=0; i<n; i++){
cout << a[i] << " ";
}
return 0;
}
有帮助，赞一个