from -> introdution to algorithms
随机化，即将partition 的哨兵随机化， 从而来平衡时间复杂度。
贴个代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
int a[100], n;
int partition(int l, int r){
int i = l - 1, j, x = a[r], t;
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;
}
int rand_partition(int l, int r){
int k = rand() % (r - l + 1) + l, t; //在l 和 r 之间随即一个下标，和哨兵交换 其他的和普通的qsort 是一样的。
t = a[k];a[k] = a[r];a[r] = t;
return partition(l, r);
}
void qsort(int l, int r){
int q;
if(l < r){
q = rand_partition(l, r);
qsort(l, q - 1);
qsort(q + 1, r);
}
}
int main(){
freopen("qsort_rand.in", "r", stdin);
freopen("qsort_rand.out", "w", stdout);
int i;
while(scanf("%d", &n) != -1){
srand(time(NULL));
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;
}