利用分治策略优化快速排序

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];}
};