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

1. 基本思想

    分治快速排序（Quick Sort）是一种基于分治法的排序算法，采用递归的方式将一个数组分割成小的子数组，并通过交换元素来使得每个子数组元素按照特定顺序排列，最终将整个数组排序。

快速排序的基本步骤：

选择基准元素：从数组中选择一个元素作为基准（pivot）。分区操作：将数组分成两个部分，左边的部分所有元素都小于基准元素，右边的部分所有元素都大于基准元素。此时基准元素已经排好序。递归排序：对基准元素左侧和右侧的子数组递归进行快速排序。

快速排序的核心思想：

分治法：通过每次选择一个基准元素，将数组分割成两个子数组，然后递归地对两个子数组进行排序。每次选择基准元素后，通过分区将数组划分为两个部分，左侧部分的元素都小于基准，右侧部分的元素都大于基准。递归对子数组进行排序，直到每个子数组的长度为 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 小（大）元素的部分进行排序，而不需要对整个数组进行排序，因此它的时间复杂度通常较低。

快速选择的核心思想是：

与快速排序一样，通过选择一个“基准”元素并进行分区（Partition）操作，将数组分成左右两个部分。如果基准元素的位置正好是 k，则基准元素即为第 k 小的元素。如果基准元素的位置小于 k，则继续在右侧子数组中查找第 k 小元素。如果基准元素的位置大于 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]; } };