^{<noscript id="2mvlm"></noscript>}

快速排序Java實現(xiàn)

2019-11-17 04:04:49

字體：大中小

供稿：網(wǎng)友

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("請輸入比較的數(shù)的個數(shù)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("排序后的數(shù)如下：");
  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));//產(chǎn)生處于p和r之間的隨機數(shù)
  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基本數(shù)據(jù)類型與其封裝類