归并排序

NoGift

2023-08-15 14:37:04

发布于：河北

2阅读

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;
}