快速排序

算法思想

每一輪在數組相應的范圍上隨機找一個元素進行劃分，將不大于它的所有元素都放到左邊，將大于它的元素都放到右邊。在左右兩個子數組上不斷地遞歸，直到整個數組上有序。
注意：實現時選擇的時參考荷蘭國旗問題優化后的快排算法，它會在一次劃分中維護一個包含所有等于劃分標準元素的區間，保證小于該數的都在區間左側，大于該數的都在區間右側。這樣的做法，在一定程度上能夠減少劃分次數。

穩定性分析

快速排序是不穩定的，它涉及到拆分區間，無法保證相等的數一定在同一個區間上被處理完成，也就無法保證它們的相對次序不發生變化。

具體實現

// 交換數組中的兩個元素
private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}// 全局變量 first 表示等于當前元素的第一個下標位置，last 表示最后一個
public static int first, last;private void quickSort(int[] arr, int left, int right) {// 無法構成區間，直接返回if (left >= right) {return;}// 在合法范圍內隨機一個元素作為劃分標準int pivot = arr[left + (int) (Math.random() * (right - left + 1))];// 劃分并遞歸處理左右子數組partition(arr, left, right, pivot);quickSort(arr, left, first - 1);quickSort(arr, last + 1, right);
}public void partition(int[] arr, int left, int right, int pivot) {first = left;last = right;int cur = left;while (cur <= last) {if (arr[cur] == pivot) {cur++; // 當前元素等于劃分標準，不作處理并后移指針} else if (arr[cur] < pivot) {swap(arr, first++, cur++); // 小于劃分標準，交換且分別后移兩個指針} else {swap(arr, cur, last--); // 大于劃分標準，交換并前移記錄最后一個當前元素的指針}}
}

隨機選擇

算法思想

隨機選擇是基于快排的劃分操作，能夠快速地確定一個數在數組中排序后的理論位置。這部分內容其實和排序關系不大，但是與快排有很大的關聯，可以放在一起整理。

實踐案例：Leetcode 215. 數組中的第K個最大元素

class Solution {public int findKthLargest(int[] nums, int k) {return randomizedSelect(nums, nums.length - k);}// 全局變量 first 表示等于當前元素的第一個下標位置，last 表示最后一個public static int first, last;public int randomizedSelect(int[] arr, int cur) {int res = 0;for (int left = 0, right = arr.length - 1; left <= right;) {partition(arr, left, right, arr[left + (int) (Math.random() * (right - left + 1))]);if (cur < first) {right = first - 1;  // 當前下標小于維護的第一個下標，到左邊區間中找} else if (cur > last) {left = last + 1; // 當前下標大于維護的最后一個下標，到右邊區間中找} else {res = arr[cur]; // 當前下標在維護的范圍內，記錄結果break;}}return res;}// 交換數組中的兩個元素private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public void partition(int[] arr, int left, int right, int pivot) {first = left;last = right;int cur = left;while (cur <= last) {if (arr[cur] == pivot) {cur++; // 當前元素等于劃分標準，不作處理并后移指針} else if (arr[cur] < pivot) {swap(arr, first++, cur++); // 小于劃分標準，交換且分別后移兩個指針} else {swap(arr, cur, last--); // 大于劃分標準，交換并前移記錄最后一個當前元素的指針}}}
}

梳理總結

快速排序的理論復雜度是 $O(NlogN)$，它通過劃分來不斷減小問題規模從而快速解決問題。但是實踐中存在能使快排退化到 $O(N^2)$ 的陰間待排序列，因此需要通過隨機劃分標準這個手段來讓時間復雜度盡可能地穩定在 $O(NlogN)$。
隨機選擇算法，本質上是根據不同的標準，維護相應的數值區間。它能夠在理論實踐復雜度 $O(N)$ 且不需要額外空間的情況下找出數組中第 $K$ 大的數。

后記

使用 Leetcode 912. 排序數組 進行測試，隨機快速排序能夠比較高效地完成任務。
實際運行下來和歸并排序之間都有一些差距，猜測原因是隨機操作的耗時很大，并且 Leetcode 平臺上專門設置了卡快排的用例。