随机快速排序算法:
还没怎么整明白,有点晕
Java语言:
import java.util.*;
public class Test {
int[] x = {3,7,5,6,4,9,8,1};
int comps = 0;
void quicksort(int l, int u)
{
int i, m;
if (l >= u) return;
swap(l, getRandom(l, u));
m = l;
comps += u - 1;
for (i = l+1; i <= u; i++){
//comps++;
if (x[i] < x[l])
swap(++m, i);
}
swap(l, m);
quicksort(l, m-1);
quicksort(m+1, u);
}
void swap(int a,int b){
int temp = x[a];
x[a] = x[b];
x[b] = temp;
}
int getRandom(int min,int max){
return (int)(Math.random()*(max-min+1)) + min;
//Math.round(Math.random()*(Max-Min)+Min);
}
public static void main(String[] args) {
Test t = new Test();
System.out.println(Arrays.toString(t.x));
t.quicksort(0,t.x.length - 1);
System.out.println(t.comps);
System.out.println(Arrays.toString(t.x));
}
}