快排（改進版）

經典快排每次隻解決一個數：小于等于這個數放左邊，大于的放右邊。

而改進的快排選中一個基準數，将數組分為三個區：小于區，等于區，大于區。這就解決了經典快排每次隻解決一個數的問題。

public class QuilkSort {
    public static void main(String[] args) {
        int[] arr = {,,,,,,,,};
        quilkSort(arr);
        for(int i = ; i < arr.length; i++) {
            System.out.print(arr[i] + "  ");
        }

    }
    public static void quilkSort(int[] arr) {
        if(arr == null || arr.length < ) 
            return;
        quilkSort(arr,,arr.length-);
    }

    public static void quilkSort(int[] arr, int l, int r) {
        if(l < r) {
            swap(arr, l + (int) (Math.random() * (r - l + )), r); //随機快排代碼
            int[] p = partition(arr, l, r);
            quilkSort(arr, l, p[] - );
            quilkSort(arr, p[] + , r);
        }
    }
    public static int[] partition(int[] arr, int l, int r) { //預設選數組最後一個數為基準數
        int less = l - ; //小于區下标
        int more = r + ; //大于區下标
        int cur = l;
        while(cur < more) { 
            if(arr[cur] < arr[r]) { //小于區向後擴一個位置
                swap(arr, ++less, cur++);
            }else if(arr[cur] > arr[r]) {
                swap(arr, --more, cur);  //大于區向前擴一個位置
            }else 
                cur++;
        }
        return new int[]{ less + , more -  }; //傳回等于值數組下标
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
           

swap(arr, l + (int) (Math.random() * (r - l + 1)), r)加上這句代碼變為随機快排，每次從數組中随機選一個數字作為基準數。