專欄：算法的魔法世界

個人主頁：手握風云

目錄

一、快速排序

二、例題講解

2.1.?顏色分類

2.2.?排序數組

2.3.?數組中的第K個最大元素

2.4.?庫存管理 III

---

一、快速排序

????????分治，簡單理解為“分而治之”，將一個大問題劃分為若干個子問題，直到這個子問題能夠快速解決。我們之前的快速排序是選出一個數作為基準值，然后將一個數組劃分為兩個子序列，一個序列<=基準值，另一個>基準值。但這種算法在數據特別大的時候是會超時的。所以我們這里要使用更優秀的三塊劃分和隨機選擇基準元素的算法。

二、例題講解

2.1.?顏色分類

? ? ? ? 這道題我們可以參照移動零里面的劃分策略。移動零里面是利用雙指針將數組分為0區域和非0區域，這道題我們也可以使用三個指針left、right、i來將其劃分為0、1、2區域。其中i用來遍歷數組，left用來標記0區域的最右側，right用來標記2區域的最左側。

? ? ? ? 接下來進行分類討論：如果nums[i]=0，我們讓nums[left+1]與nums[i]進行交換，然后i++，left++，就能保證[left+1,i-1]區間還都是1，還可能有一種極端情況，就是i=left+1，自身與自身進行交換，還是得需要left和i++，綜上我們就可以寫成nums[++left]與nums[i++]進行交換。如果nums[i]=1，我們直接就可以i++就可以。如果nums[i]=2時，right的移動也可以參照上面left的處理，--right，但i不能++，因為i右側是未遍歷的區間，如果i++，就會跳過這個元素。當i=right時，結束循環。

? ? ? ? 完整代碼實現：

class Solution {public void sortColors(int[] nums) {int left = -1, right = nums.length, i = 0;while (i < right) {if (nums[i] == 0)swap(nums, ++left, i++);else if (nums[i] == 1)i++;else if (nums[i] == 2)swap(nums, --right, i);}}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

2.2.?排序數組

? ? ? ? 這道題如果我們直接采用之前的快排思想是會超時的，因為如果數組里的元素都等于基準值key，這樣數組元素就會跑到數組的最右側，導致時間復雜度會退化成。

? ? ? ? 我們接下來利用數組分三塊的思想，將其劃分為3個區域，<=key，=key，>=key。這樣當基準值都等于key時，時間復雜度直接降為。

? ? ? ? 接下來就是如何隨機選擇基準值。我們需要在數組下標中等概率地選擇一個下標，那么我們就可以利用隨機數種子，利用公式r%(right-left+1)+left求出隨機下標。

? ? ? ? 完整代碼實現：

class Solution {public int[] sortArray(int[] nums) {Quicksort(nums, 0, nums.length - 1);return nums;}private void Quicksort(int[] nums, int l, int r) {if (l >= r) return;//作為遞歸結束的條件//數組分三塊int key = nums[new Random().nextInt(r - l + 1) + l];int left = l - 1, right = r + 1, i = l;while (i < right) {if (nums[i] < key) swap(nums, ++left, i++);else if (nums[i] == key) i++;else if (nums[i] > key) swap(nums, --right, i);}Quicksort(nums, l, left);Quicksort(nums, right, r);}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

2.3.?數組中的第K個最大元素

? ? ? ? 因為這道題讓我們用時間復雜度為，所以我們的思路很明顯要使用快速選擇排序，也就是上一題的數組分三塊與隨機選擇基準元素。那么這個第K大的元素就有可能落在三個區域內，我們設三個區域的元素個數分別為a、b、c。如果c>=k，那我們就直接去>key的這個區域去尋找；如果b+c>=k，就直接返回key；如果前兩個都不成立，就去<key這個區間去尋找第k-b-c大的元素。

? ? ? ? 完整代碼實現：

class Solution {public int findKthLargest(int[] nums, int k) {return Quicksort(nums, 0, nums.length - 1, k);}private int Quicksort(int[] nums, int l, int r, int k) {if (l == r) return nums[l];//隨機選擇基準元素int key = nums[new Random().nextInt(r - l + 1) + l];//根據基準元素，把數組分為三塊int left = l - 1, right = r + 1, i = l;while (i < right) {if (nums[i] < key) swap(nums, ++left, i++);else if (nums[i] == key) i++;else if (nums[i] > key) swap(nums, --right, i);}//分類討論//區間:[l,left],[left+1,right-1],[right,r]int b = right - left - 1, c = r - right + 1;if (c >= k) return Quicksort(nums, right, r, k);else if (b + c >= k) return key;else return Quicksort(nums, l, left, k - b - c);}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

2.4.?庫存管理 III

? ? ? ? 題目就是求數組中的最小的cnt個數。第一種解法，可以使用Arrays.sort()方法來對數組進行排序，找出前k個元素；第二種解法，利用大根堆，創建一個大小為k的大根堆，將數組的前k個元素丟進大根堆中，然后再將數組剩余的元素與堆頂元素比較，如果小就交換并調整堆，最后堆里面就是最小的k個數；第三個解法，就是快速選擇算法。第一種解法的時間復雜度為，第二種解法的時間復雜度為，第三中解法的時間復雜度為。

? ? ? ? 按照上一題的思路，將數組分為三塊，三個區間內元素的個數分別為a、b、c。如果a>cnt，那么我們只需要去<key的區間去尋找；如果a+b>=cnt，此時的cnt一定是大于a的，那么最小的cnt個數，一定位于左側兩個區間，而中間區間又都是等于key的，所以不需要遞歸，直接++；如果前兩個都不成立，直接去最右側的區間去尋找第cnt-a-b個元素。

? ? ? ? 完整代碼實現：

class Solution {public int[] inventoryManagement(int[] stock, int cnt) {Quicksort(stock,0,stock.length - 1,cnt);int[] ret = new int[cnt];for (int i = 0; i < cnt; i++) {ret[i] = stock[i];}return ret;}private void Quicksort(int[] nums, int l, int r, int k) {if(l >= r) return;//隨機獲取基準元素int key = nums[new Random().nextInt(r - l + 1) + l];int left = l - 1,right = r + 1,i = l;//數組分三塊while(i < right){if(nums[i] < key) swap(nums,++left,i++);else if (nums[i] == key) i++;else if (nums[i] > key) swap(nums,--right,i);}//分類討論int a = left - l + 1,b = right - left - 1;if(a > k) Quicksort(nums,l,left,k);else if (a + b >= k) return;else Quicksort(nums,right,r,k - a - b);}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}