1169: 绝对值排序

解题思路:归并排序

注意事项:

参考代码:

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 1e3 + 10;
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, k = 0;
	while(i <= mid && j <= r){
		if(abs(a[i]) >= abs(a[j])) b[k ++] = a[i++];
		else b[k ++] = a[j++];
	}
	while(i <= mid) b[k ++] = a[i ++];
	while(j <= r) b[k ++] = a[j ++];
	for(int t = l, p = 0; t <= r; t ++,p ++){
		a[t] = b[p];
	}	
}
int main()
{
	int n;
	while(cin >> n && n > 0){
		memset(a, 0, sizeof a);
		for(int i = 0; i < n; i ++) cin >> a[i];
		int l = 0, r = n - 1;
		merge_sort(l, r);
		for(int i = 0;  i < n; i ++) cout << a[i] <<' '; 
	}
	
	return 0;
}