1. //  随机找一个数和最后一个数做交换，然后做划分值。划分出来的位置变了概率事件。 O（N*logN）
    2.     public static void QuickSort(int[] arr) {
    3.         if (arr == null || arr.length < 2) {
    4.             return;
    5.         }
    6.         Process(arr, 0, arr.length - 1);
    7.     }
    9.     public static void Process(int[] arr, int L, int R) {
    10.         if (L >= R) {
    11.             return;
    12.         }
    13.         // L~R随机选取
    14.         Swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
    15.         int[] equalArea = netherlandsFlag(arr, L, R); // 划分等于区域的左边界,右边界
    16.         Process(arr, L, equalArea[0] - 1);// <区
    17.         Process(arr, equalArea[1] + 1, R);// >区
    18.     }
    21.     public static int[] netherlandsFlag(int[] arr, int L, int R) {
    22.         if (L > R) { // L...R L>R
    23.             return new int[] { -1,-1 };
    24.         }
    25.         if (L == R) {
    26.             return new int[] {  L,R };
    27.         }
    28.         int less = L - 1; // < 区 左边界
    29.         int more = R; // > 区 右边界
    30.         int index = L;
    31.         while (index < more) { // 当前位置index和 >区的边界撞上停止
    32.             if (arr[index] == arr[R]) {   
    33.                 index++;
    34.             } else if (arr[index] < arr[R]) {
    35. //            [index]和<区的下一个数交换，然后<区向右扩一个位置,index++
    36.                 Swap(arr,  ++less,index++);
    37.             } else { 
    38. //            [index]和>区前一个数交换，>区左扩一个位置，index不变因为没有交换完的数没有看过        
    39.                 Swap(arr, index, --more);
    40.             }
    41.         }
    42.         Swap(arr, more, R); // <[R]   =[R]   >[R] ,和最后一位划分指做交换
    43.         // less+1因为小于区域需要加一 才能到等于区域上，而大于区域已经和index撞上了不用加
    44.         return new int[] { less + 1, more };
    45.     }
    47.     public static void Swap(int[] arr, int i, int j) {
    48.         int tmp = arr[i];
    49.         arr[i] = arr[j];
    50.         arr[j] = tmp;
    51.     }