快速排序Java实现

核心提示： package quickSort;import java.util.Random;import java.util.Scanner;public class QuickSort { public static int n = 0; public static int[] array = null; public

 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;
}
}