1. 基本思想

? ? 分治快速排序（Quick Sort）是一種基于分治法的排序算法，采用遞歸的方式將一個數組分割成小的子數組，并通過交換元素來使得每個子數組元素按照特定順序排列，最終將整個數組排序。

快速排序的基本步驟：

1. 選擇基準元素：從數組中選擇一個元素作為基準（pivot）。
2. 分區操作：將數組分成兩個部分，左邊的部分所有元素都小于基準元素，右邊的部分所有元素都大于基準元素。此時基準元素已經排好序。
3. 遞歸排序：對基準元素左側和右側的子數組遞歸進行快速排序。

快速排序的核心思想：

• 分治法：通過每次選擇一個基準元素，將數組分割成兩個子數組，然后遞歸地對兩個子數組進行排序。
• 每次選擇基準元素后，通過分區將數組劃分為兩個部分，左側部分的元素都小于基準，右側部分的元素都大于基準。
• 遞歸對子數組進行排序，直到每個子數組的長度為 1 或 0，排序完成。

// 分區函數，返回基準元素的正確位置
int Partition(vector<int>& arr, int low, int high) {int pivot = arr[high];  // 選擇最后一個元素作為基準int i = low - 1;  // i 是小于基準元素的子數組的最后一個元素的索引// 遍歷數組，將小于基準的元素移動到數組的前面for (int j = low; j < high; ++j) {if (arr[j] < pivot) {++i;swap(arr[i], arr[j]);}}// 將基準元素放到正確的位置swap(arr[i + 1], arr[high]);return i + 1;  // 返回基準元素的索引
}// 快速排序函數
void QuickSort(vector<int>& arr, int low, int high) {if (low < high) {// 找到基準元素的索引int pi = Partition(arr, low, high);// 遞歸排序基準元素左邊和右邊的子數組QuickSort(arr, low, pi - 1);  // 排序左邊子數組QuickSort(arr, pi + 1, high); // 排序右邊子數組}
}

?2. 快速選擇算法

? ? 快速選擇算法（Quickselect） 是一種基于快速排序（Quick Sort）的算法，用于在未排序的數組中找到第 k 小（大）的元素。與快速排序不同，快速選擇只對包含第 k 小（大）元素的部分進行排序，而不需要對整個數組進行排序，因此它的時間復雜度通常較低。

快速選擇的核心思想是：

1. 與快速排序一樣，通過選擇一個“基準”元素并進行分區（Partition）操作，將數組分成左右兩個部分。
2. 如果基準元素的位置正好是 k，則基準元素即為第 k 小的元素。
3. 如果基準元素的位置小于 k，則繼續在右側子數組中查找第 k 小元素。
4. 如果基準元素的位置大于 k，則繼續在左側子數組中查找第 k 小元素。

通過將數組分成三個部分：小于基準、等于基準、大于基準，從而更有效地找到第 k 小的元素。相較于傳統的快速選擇算法，使用三個部分分區可以加速查找過程，特別是在處理重復元素時。

下面是一個示例，這類問題可以以此為模板，通過適當修改來實現不同的目標。?

int qsort(vector<int>& nums, int l, int r, int k){if(l == r) return nums[l];//1.隨機選擇基準數int key = getRandom(nums, l, r);//2.根據基準數將數組分成三組int left = l - 1, right = r + 1, i = l;while(i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]); }//3.分情況討論int c = r - right + 1, b = right - left - 1;if(c >= k)return qsort(nums, right, r, k);else if(b + c >= k) return key;else  return qsort(nums, l, left, k - b - c);}int getRandom(vector<int>& nums, int left, int right){int r = rand();return nums[r % (right - left) + left];}

3. 顏色分類

解法：三指針

排序時數組被分成四個部分，[0, left] 區間都是0，(left, i)區間都是1，[i, right]區間是未排序的部分，[right , n - 1]區間都是2.

排序完成后，i與right相等，數組被分成三個部分[0, left]都是1，(left, i)都是0，[right , n - 1]都是2

class Solution {
public:void sortColors(vector<int>& nums) {int i = 0, n = nums.size();int left = -1, right = n;while(i < right){if(nums[i] == 0) swap(nums[i++], nums[++left]);else if(nums[i] == 1) i++;else if(nums[i] == 2) swap(nums[i], nums[--right]);}}
};

75. 顏色分類 - 力扣（LeetCode）

4.? 排序數組

使用將數組分成三部分的思想實現快排，效率會更高

class Solution {
public:vector<int> sortArray(vector<int>& nums) {srand(time(NULL));qsort(nums, 0, nums.size() - 1);return nums;}void qsort(vector<int>& nums, int l, int r){if(l >= r) return;int key = getRanNum(nums, l, r);//獲取隨機基準值int i = l, left = l - 1, right = r + 1;while(i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]);}qsort(nums, l, left);qsort(nums, right, r);}int getRanNum(vector<int>& nums, int left, int right){int r = rand();return nums[r % (right - left) + left];}
};

912. 排序數組 - 力扣（LeetCode）

5. 數組中第k個最大元素

快速選擇算法

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {srand(time(NULL));return qsort(nums, 0, nums.size() - 1, k);}int qsort(vector<int>& nums, int l, int r, int k){if(l == r) return nums[l];//返回條件//1.隨機選擇基準數int key = getRandom(nums, l, r);//2.根據基準數將數組分成三組int left = l - 1, right = r + 1, i = l;while(i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]); }//3.分情況討論int c = r - right + 1, b = right - left - 1;if(c >= k)return qsort(nums, right, r, k);else if(b + c >= k) return key;else  return qsort(nums, l, left, k - b - c);}int getRandom(vector<int>& nums, int left, int right){int r = rand();return nums[r % (right - left) + left];}
};

215. 數組中的第K個最大元素 - 力扣（LeetCode）

6. 庫存管理

法一：排序 O(nlogn)

法二：堆排序 O(nlogk)

法三：快速選擇算法 O(n)

class Solution {
public:vector<int> inventoryManagement(vector<int>& stock, int cnt) {srand(time(NULL));qsort(stock, 0, stock.size() - 1, cnt);return {stock.begin(), stock.begin() + cnt};}void qsort(vector<int>& stock,int l, int r, int cnt){if(l == r) return;//1.隨機選擇基準數int key = getRandom(stock, l, r);//2.根據基準數將數組分成三組int left = l - 1, right = r + 1, i = l;while(i < right){if(stock[i] < key) swap(stock[++left], stock[i++]);else if(stock[i] == key) i++;else swap(stock[--right], stock[i]); }//3.分情況討論int a = left - l + 1, b = right - left - 1;if(cnt < a) qsort(stock, l, left, cnt);else if(cnt <= a + b) return;else qsort(stock, right, r, cnt - a - b);}int getRandom(vector<int>& stock, int left, int right){int r = rand();return stock[r % (right - left) + left];}
};