from -> introdution to algorithms
分治的思想。 贴个代码
#include <stdio.h>
#include <string.h>
int a[100], n;
int partition(int l, int r){
int x = a[r], i = l - 1, j, t;
//x为哨兵
//i 为两个集合(小于等于哨兵［在左边］， 大于等于哨兵［在右边］)的分界线
for(j = l; j < r; j++){
if(a[j] <= x){//若发现 小于哨兵的元素 则左边的集合长度扩展，交换。
i++;
t = a[i];a[i] = a[j];a[j] = t;
}
}i++;//转移到右边几何第一个并交换
t = a[i];a[i] = a[r];a[r] = t;
return i;//为哨兵所在位置。 保证左边和右边集合的正确划分。
}
void qsort(int l, int r){
int q;
if(l < r){
q = partition(l, r);//partition//对于搜索树来说，类似是先序遍历的。
qsort(l, q - 1);//左半部分
qsort(q + 1, r);//右半部分
//这里没有合并操作，a[l, r]已经是有序的了。
}
}
int main(){
freopen("qsort.in", "r", stdin);
freopen("qsort.out", "w", stdout);
int i, j;
while(scanf("%d", &n) != -1){
for(i = 1; i <= n; i++)
scanf("%d", &a[i]);
qsort(1, n);
for(i = 1; i <= n; i++)
printf("%d ", a[i]);
puts("");
}
return 0;
}