Quicksort（快速排序法）

Quicksort（快速排序）

快速排序步驟：

1、從數列中挑出一個元素，稱為 “基準”（pivot）;

2、重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處于數列的中間位置。這個稱為分區（partition）操作；

3、遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序；

實作的代碼如下：

public class Quicksort {

public static void quick(int[] a,int start,int end){

int i=start,j=end;
    if (i>=j)return;
    int tmp=a[i];
    while (i<j){ //循環條件i<j
        //循環内要有兩個循環來重複i++和j--的過程
        while (a[j]>=tmp&&i<j) j--;
        //不滿足上一條的循環條件的時候，則要進行對應指派
        a[i]=a[j];
        while (a[i]<=tmp&&i<j) i++;
        //不滿足上一條的循環條件的時候，則要進行對應指派
        a[j]=a[i];
    }
    //出外層循環時，把标準位插入在i處
    a[i]=tmp;
    //遞歸調用（自己調自己）
    quick(a,start,i-1);
    quick(a,i+1,end);
}
public static int[] randomArray(int length){
    int[] a = new int[length];
    for (int i = 0; i < a.length; i++) {
        //随機數生成
        Random r=new Random();
        a[i]=r.nextInt(100);
    }
    return a;
}
public static void main(String[] args) {
    int[] a= randomArray(60);
    System.out.println(Arrays.toString(a));
    long now=System.currentTimeMillis();
    quick(a,0,a.length-1);
    System.out.println(Arrays.toString(a));
    long used=System.currentTimeMillis()-now;
    System.out.println("花費："+used);
}