升序

2023-07-26 09:37:23

发布于：河北

7阅读

0回复

0点赞

归并排序实现。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 4;
int a[MAXN], n, tmp[MAXN];

void BACK(int l, int r, int m) {
	int i = l, j = m + 1, k = l;
	while (i <= m && j <= r) {
		if (a[i] < a[j]) tmp[k++] = a[i++];
		else tmp[k++] = a[j++];
	}
	while (i <= m) tmp[k++] = a[i++];
	while (j <= r) tmp[k++] = a[j++];
	for (int i = l; i <= r; i++) {
		a[i] = tmp[i];
	}
}

void MERGES(int l, int r) {
	if (l >= r) return ;
	int m = (l + r) / 2;
	MERGES(l, m);
	MERGES(m + 1, r);
	BACK(l, r, m);
}

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