package quickSort;
import java.util.Random;
import java.util.Scanner;
public class QuickSort {
public static int n = 0;
public static int[] array = null;
public static void main(String[] args) {
System.out.println("请输入比较的数的个数n: ");
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
array = new int[n];
Random r = new Random();
for(int i=0; i<n;) {
array[i] = r.nextInt(6000);
//System.out.print(array[i] + " ");
i++;
/*if(i%10 == 0) {
System.out.println();
}*/
}
long t = System.currentTimeMillis();
qSort(0, n-1);
System.out.println("排序所用时间为： " + (System.currentTimeMillis() - t) + "ms");
/*System.out.println("排序后的数如下：");
for(int i=0; i<n;) {
System.out.print(array[i] + " ");
i++;
if(i%10 == 0) {
System.out.println();
}
}*/
}
public static void qSort(int p, int r) {
if(p < r) {
int pt = partition(p, r);
qSort(p, pt-1);
qSort(pt+1, r);
}
}
public static int partition(int p, int r) {
int pt = (int) (p + Math.random()*(r-p));//产生处于p和r之间的随机数
int flag = array[pt];
int i=p-1;
int j=r+1;
while(true) {
while(array[++i] > flag);
while(array[--j] < flag);
if(i>=j) break;
int swap = array[i];
array[i] = array[j];
array[j] = swap;
}
array[i] = flag;
return i;
}
}