快速排序Java实现

2019-11-17 04:04:49

字体：大中小

来源：转载

供稿：网友

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

上一篇：java开源类库pinyin4j的使用

下一篇：java基本数据类型与其封装类