/********************************
* 程序名称：分治应用
* 开发时间：
*******************************/
#include <iostream>
#include <cstdio>
using namespace std;
int s[100001], b[100001];
//合并
void mergeArray(int left, int m, int right) {
int l1, r1, l2, r2, k = 0;
l1 = left;
r1 = m;
l2 = m + 1;
r2 = right;
while(l1 <= r1 && l2 <= r2) {
if(s[l1] < s[l2]) {
b[k] = s[l1];
k ++;
l1 ++;
} else {
b[k] = s[l2];
k ++;
l2 ++;
}
}
/*剩余的数合并*/
while(l1 <= r1) {
b[k] = s[l1];
k ++;
l1 ++;
}
/*剩余的数合并*/
while(l2 <= r2) {
b[k] = s[l2];
k ++;
l2 ++;
}
for(int i=0; i<k; i++) {
s[left+i] = b[i];
}
}
//排序合并
void mergeSort(int left, int right) {
int mid;
if (left < right) {
mid = (left + right) / 2;
mergeSort(left, mid); //左边排序
mergeSort(mid+1, right); //右边排序
mergeArray(left, mid, right); //左右合并
}
}
//main() star
int main() {
//code here
int n;
cin >> n;
for(int i=0; i<n; i++) {
cin >>s[i];
}
mergeSort(0, n -1);
for(int i=0; i<n; i++) {
cout << s[i] <<endl;
}
return 0;
}
测试1：
5
2 5 1 4 6
1
2
4
5
6
--------------------------------
Process exited after 4.53 seconds with return value 0
请按任意键继续. . .
测试2：
10
2 5 8 7 4 1 3 6 9 23
1
2
3
4
5
6
7
8
9
23
--------------------------------
Process exited after 7.456 seconds with return value 0
请按任意键继续. . .
