### 1.2 隨機快排
快速排序程序的整體結構也是遞歸的，其主要借助一個Partition過程完成排序工作；Partition過程的定義如下：
> 給定一個數組arr，和一個整數num。請把小于等于num的數放在數組的左邊，大于num的數放在數組的右邊。
>
> 要求：空間復雜度為O(1)，時間復雜度為O(n)
完成Partition過程只需要兩個指針，一個指針用于遍歷數組的元素，一個指針用來指向小于等于數組區域的最右邊的下標leftBorder，當發現arr\[i\] < num的時候，交換leftBorder+1和i位置的值。
~~~
?public static int partition(int[] nums, int num) {
? ? ?int leftBorder = 0;
? ? ?int i = 0;
? ? ?while (i < nums.length) {
? ? ? ? ?if (nums[i] <= num) {
? ? ? ? ? ? ?// 與左邊界的第一個值交換
? ? ? ? ? ? ?swap(nums, leftBorder++, i);
? ? ? ? }
? ? ? ? ?i++;
? ? }
? ? ?return leftBorder - 1;
?}
~~~
可以Partition進一步優化，將數組arr根據num分為三個區域，小于左邊，等于中間，大于右邊；這就是經典的荷蘭國旗問題，完成該過程需要兩個指針，一個指針指向小于等于數組的右邊界leftBorder，一個指針指向大于數組的左邊界rightBorder，其初始化分別為：leftBorder=0，rightBorder=arr.length；算法流程如下：
* 當arr\[i\] == num，i++；
* 當arr\[i\] < num，arr\[i\]與小于區域右一個交換，小于區域右擴，i++；
* d當arr\[i\] > num，arr\[i\]與大于區域左一個交換，大于區域左擴，i原地不動（這是因為需要重新判斷新換過來的元素是否滿足條件）
與partition過程不同的是，荷蘭國旗問題返回等于區域左右兩個邊界的位置。
~~~
? ? ?public static int[] netherlandsFlag(int[] nums, int num, int L, int R) {
? ? ? ? ?if (L > R) {
? ? ? ? ? ? ?return new int[]{-1, -1};
? ? ? ? }
? ? ? ? ?if (L == R) {
? ? ? ? ? ? ?return new int[]{L, R};
? ? ? ? }
? ? ? ? ?int leftBorder = L - 1, rightBorder = R + 1;
? ? ? ? ?int i = L;
? ? ? ? ?while (i < rightBorder) {
? ? ? ? ? ? ?if (nums[i] == num) {
? ? ? ? ? ? ? ? ?i++;
? ? ? ? ? ? } else if (nums[i] < num){
? ? ? ? ? ? ? ? ?// 擴充小于數組
? ? ? ? ? ? ? ? ?swap(nums, i++, ++leftBorder);
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ?// 擴充大于數組
? ? ? ? ? ? ? ? ?swap(nums, i, --rightBorder);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? ?return new int[]{leftBorder + 1, rightBorder - 1};
? ? }
~~~
荷蘭國旗問題過程與partition過程相比用于快排可以減少遞歸的次數。
**快排1.0**
選擇最后一個元素最為partition過程的基準元素，對數組分成大于x的組和小于等于x的組，這個過程就可以確定x在排序過程中的位置。之后在從該位置進行左右遞歸。
~~~
?public static void quickSort1(int[] nums) {
? ? ?if (nums == null || nums.length < 2) {
? ? ? ? ?return;
? ? }
? ? ?process1(nums, 0, nums.length - 1);
?}
??
?public static void process1(int[] nums, int L, int R) {
? ? ?if (L >= R) {
? ? ? ? ?return;
? ? }
? ? ?// 選取nums[R]作為基準元素
? ? ?int mid = partition(nums, nums[R], L, R);
? ? ?process1(nums, L, mid - 1);
? ? ?process1(nums, mid + 1, R);
?}
~~~
**快排2.0**
利用荷蘭國旗過程，將數組分為三組，可以一次性確定相等數值的位置，較少遞歸次數，但是時間復雜度任然是不變的。
~~~
?/**
? ? ? * 利用荷蘭國旗過程的快排
? ? ? * @param nums
? ? ? */
?public static void quickSort2(int[] nums) {
? ? ?if (nums == null || nums.length < 2) {
? ? ? ? ?return;
? ? }
? ? ?process2(nums, 0, nums.length - 1);
?}
??
?public static void process2(int[] nums, int L, int R) {
? ? ?if (L >= R) {
? ? ? ? ?return;
? ? }
? ? ?int[] ints = netherlandsFlag(nums, nums[R], L, R);
? ? ?process2(nums, L, ints[0] - 1);
? ? ?process2(nums, ints[1] + 1, R);
?}
~~~
快排1.0和快排2.0如果按照最差的情況，即數組本身就是排好序的，其時間復雜度為O(n^2)。
**快排3.0**
隨機選一個數作為劃分值，然后將該值與最后一個值交換。
~~~
?/**
? ? ? * 隨機快排
? ? ? * @param nums
? ? ? */
?public static void quickSort3(int[] nums) {
? ? ?if (nums == null || nums.length < 2) {
? ? ? ? ?return;
? ? }
? ? ?process3(nums, 0, nums.length - 1);
?}
??
?public static void process3(int[] nums, int L, int R) {
? ? ?if (L >= R) {
? ? ? ? ?return;
? ? }
? ? ?// 隨機選擇一個元素
? ? ?int randomIndex = (int)(Math.random() * (R - L + 1)) + L;
? ? ?int[] ints = netherlandsFlag(nums, nums[randomIndex], L, R);
? ? ?process3(nums, L, ints[0] - 1);
? ? ?process3(nums, ints[1] + 1, R);
?}
~~~
這種情況下好的情況的時間復雜度為：
T(n) = 2 \* T(n/2) + O(n)，由主方法可知其時間復雜度為O(nlgn)。用概率來計算其時間復雜度：最后得到平均時間復雜度為：O(nlgn)。不用最差情況考慮就是因為程序在運行的時候是隨機選擇，最差情況發生的概率并不大。
隨機快排的時間復雜度分析：
1. 劃分值越靠近中間，性能越好，越靠近兩邊，性能越差。
2. 隨機選一個數進行劃分的目的就是讓好情況和差情況都變成概率時間。
3. 把每一種情況都列出來，會有每種情況下的時間復雜度，但概率都為1/N。
4. 把所有的情況都考慮下去，時間復雜度就是這種概率模型下的長期期望，通過數學公式的推導，其時間復雜度為O(nlgn)，空間復雜度為O(lgn)。
小驗證：
~~~
?public static void main(String[] args) {
? ? ? ? Random random = new Random();
? ? ? ? // 使用partition過程的快排時間
? ? ? ? long start = System.currentTimeMillis();
? ? ? ? int[] nums = new int[100000];
? ? ? ? for (int i = 0; i < 10000; i++) {
? ? ? ? ? ? for (int j = 0; j < nums.length; j++) {
? ? ? ? ? ? ? ? nums[j] = random.nextInt(100000);
? ? ? ? ? ? }
? ? ? ? ? ? quickSort1(nums);
? ? ? ? }
? ? ? ? long end = System.currentTimeMillis();
? ? ? ? System.out.println("partition過程的快排時間為：" + (end - start) / 1000.0 + "s");
??
? ? ? ? // 使用netherlandsFlag過程的快排時間
? ? ? ? start = System.currentTimeMillis();
? ? ? ? for (int i = 0; i < 10000; i++) {
? ? ? ? ? ? for (int j = 0; j < nums.length; j++) {
? ? ? ? ? ? ? ? nums[j] = random.nextInt(100000);
? ? ? ? ? ? }
? ? ? ? ? ? quickSort2(nums);
? ? ? ? }
? ? ? ? end = System.currentTimeMillis();
? ? ? ? System.out.println("netherlandsFlag過程的快排時間為：" + (end - start) / 1000.0 + "s");
??
? ? ? ? // 使用隨機過程的快排時間
? ? ? ? start = System.currentTimeMillis();
? ? ? ? for (int i = 0; i < 10000; i++) {
? ? ? ? ? ? for (int j = 0; j < nums.length; j++) {
? ? ? ? ? ? ? ? nums[j] = random.nextInt(100000);
? ? ? ? ? ? }
? ? ? ? ? ? quickSort3(nums);
? ? ? ? }
? ? ? ? end = System.currentTimeMillis();
? ? ? ? System.out.println("隨機快排過程的快排時間為：" + (end - start) / 1000.0 + "s");
? ? }
~~~
結果：
~~~
?partition過程的快排時間為：106.185
?netherlandsFlag過程的快排時間為：118.341
?隨機快排過程的快排時間為：130.55
~~~
結論：在數據本身就是均勻的情況下，partition過程反倒更合適！
但是如果數組原本就是逆序的，隨機快排的優勢就可以大大的顯示出來
~~~
?partition過程的快排時間為：352.794s
?netherlandsFlag過程的快排時間為：1017.239s
?隨機快排過程的快排時間為：6.513s
~~~
