归并排序【模板】

谁来教我C++

2023-08-15 14:57:13

发布于：浙江

13阅读

0回复

0点赞

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+5;

int n,m,k,T;
int a[N];
int temp[N];

void init(int l1,int r1, int l2 , int r2){
	int l = l1, r = l2, cnt = 0;
	while(l <= r1 && r <= r2){
		if(a[l] < a[r])	temp[cnt++] = a[l++];
		else temp[cnt++] = a[r++];
	}
	
	while(l <= r1)	temp[cnt++] = a[l++];
	while(r <= r2)	temp[cnt++] = a[r++];
	
	for(int i=0;i<cnt;i++){
		a[l1+i] = temp[i];
	}
}

void solve(int l,int r){
	if(l >= r)	return;
	
	int mid = l + r >> 1;
	solve(l,mid);
	solve(mid+1,r);
	
	init(l, mid, mid+1, r);
}

int main(){
	
	cin >> n;
	for(int i=1;i <= n;i++){
		cin >> a[i];
	}
	solve(1,n);
	for(int i=1;i<=n;i++){
		cout << a[i]<< " ";
	}
	
	return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论