快速排序及优化

上一篇 / 下一篇 2011-05-03 15:39:45 / 个人分类：技术

publicvoidqsort7(int[] x,intp,intr) {
if(p >= r)
return;
// 在数组大小小于7的情况下使用快速排序
if(r - p +1<7) {
for(inti = p; i <= r; i++) {
for(intj = i; j > p && x[j -1] > x[j]; j--) {
swap(x, j, j -1);
}
}
return;
}
// 选择中数，与qsort6相同。
intlen = r - p +1;
intm = p + (len >>1);
if(len >7) {
intl = p;
intn = p + len -1;
if(len >40) {
ints = len /8;
l = med3(x, l, l + s, l +2* s);
m = med3(x, m - s, m, m + s);
n = med3(x, n -2* s, n - s, n);
}
m = med3(x, l, m, n);
}
intv = x[m];
// a,b进行左端扫描，c,d进行右端扫描
inta = p, b = a, c = p + len -1, d = c;
while(true) {
// 尝试找到大于pivot的元素
while(b <= c && x[b] <= v) {
// 与pivot相同的交换到左端
if(x[b] == v)
swap(x, a++, b);
b++;
}
// 尝试找到小于pivot的元素
while(c >= b && x[c] >= v) {
// 与pivot相同的交换到右端
if(x[c] == v)
swap(x, c, d--);
c--;
}
if(b > c)
break;
// 交换找到的元素
swap(x, b++, c--);
}
// 将相同的元素交换到中间
ints, n = p + len;
s = Math.min(a - p, b - a);
vecswap(x, p, b - s, s);
s = Math.min(d - c, n - d -1);
vecswap(x, b, n - s, s);
// 递归调用子序列
if((s = b - a) >1)
qsort7(x, p, s + p -1);
if((s = d - c) >1)
qsort7(x, n - s, n -1);
}