快速排序的原理是什么？

快速排序力扣题（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 高的元素。你可以按 任意顺序 返回答案。