快速排序的原理是什么？

快速排序力扣题（leetcode） 215. 数组中的第K个最大元素 难度：中等 相关标签：数组、分治、快速选择、排序、堆（优先队列） 题目： 给定整数数组 nums 和整数 k，请返回数组中第 k个最大的元素。 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1: 输入: [3,2,1,5,6,4], k = 2 输出: 5 示例 2: 输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4 提示： 1 <= k <= nums.length <= 105 -104 <= nums[i] <= 104 代码： class Solution { public: int quick_sort(vector<int>& q, int l, int r, int k) { if (l >= r) return q[l]; int i = l - 1, j = r + 1, x = q[(l + r)/2]; while (i < j) { do i++; while (q[i] < x); do j--; while (q[j] > x); if (i < j) swap(q[i], q[j]); } if (k <= j - l + 1) return quick_sort(q, l, j, k); else return quick_sort(q, j + 1, r, k - (j - l + 1)); } int findKthLargest(vector<int>& nums, int k) { int n = nums.size(); return quick_sort(nums, 0, n-1, n-k+1); } }; //模板如下： // int quick_sort(int q[], int l, int r, int k) // { // if (l >= r) return q[l]; // int i = l - 1, j = r + 1, x = q[l + r >> 1]; // while (i < j) // { // do i++; // while (q[i] < x); // do j--; // while (q[j] > x); // if (i < j) swap(q[i], q[j]); // } // if (k <= j - l + 1) // return quick_sort(q, l, j, k); // else // return quick_sort(q, j + 1, r, k - (j - l + 1)); // } 相似题目 摆动排序 II中等 前 K 个高频元素中等 第三大的数简单 数据流中的第 K 大元素简单 最接近原点的 K 个点中等 找出数组中的第 K 大整数中等 找到和最大的长度为 K 的子序列简单 价格范围内最高排名的 K 样物品中等 347. 前 K 个高频元素 难度：中等 相关标签：数组、哈希表、分治、桶排序、计数、快速选择、排序、堆（优先队列） 题目： 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 示例 1: 输入：nums = [1,1,1,2,2,3], k = 2 输出：[1,2] 示例 2: 输入：nums = [1], k = 1 输出：[1] 示例 3: 输入：nums = [1,2,1,2,1,2,3,1,3,2], k = 2 输出：[1,2] 提示： 1 <= k <= nums.length <= 105 -104 <= nums[i] <= 104 k 的取值范围是 [1, 数组中不相同的元素的个数] 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的 代码： class Solution { public: // 快速选择核心函数：在数组arr[l..r]中，找到第k大的元素的位置 int quick_select(vector<pair<int, int>>& arr, int l, int r, int k) { if (l >= r) return l; // 区间只剩一个元素，返回其下标 // 分区逻辑（按频率降序，因为要找第k大） int i = l - 1, j = r + 1; int pivot = arr[(l + r) / 2].second; // 基准值：中间元素的频率 while (i < j) { do i++; while (arr[i].second > pivot); // 找小于基准的（降序） do j--; while (arr[j].second < pivot); // 找大于基准的（降序） if (i < j) swap(arr[i], arr[j]); } // 左区间元素个数：j - l + 1 int left_size = j - l + 1; if (k <= left_size) return quick_select(arr, l, j, k); // 第k大在左区间 else return quick_select(arr, j + 1, r, k - left_size); // 第k大在右区间 } vector<int> topKFrequent(vector<int>& nums, int k) { // 步骤1：统计频率 unordered_map<int, int> freq_map; for (int num : nums) freq_map[num]++; // 步骤2：转成<数字, 频率>的数组 vector<pair<int, int>> freq_arr; for (auto& pair : freq_map) freq_arr.push_back(pair); // 步骤3：快速选择找到第k大的频率的位置 int pos = quick_select(freq_arr, 0, freq_arr.size() - 1, k); // 步骤4：收集前k个高频元素 vector<int> result; for (int i = 0; i <= pos; i++) { result.push_back(freq_arr[i].first); } return result; } }; //模板 // void quick_sort(vector<int>& q, int l, int r) // { // if(l >= r) return; // int i = l-1, j = r+1, x = q[(l+r)/2]; // while(i < j) // { // do i++; while(q[i] < x); // do j--; while(q[j] > x); // if(q[i] < q[j]) swap(q[i], q[j]); // } // quick_sort(q, l, j), quick_sort(q, j+1, r); // } 相似题目 统计词频中等 数组中的第K个最大元素中等 根据字符出现频率排序中等 分割数组为连续子序列中等 前K个高频单词中等 最接近原点的 K 个点中等 按受欢迎程度排列功能中等 最多单词数的发件人中等 出现最频繁的偶数元素简单 链表频率简单