核心目标在无序数组中不用完全排序找到第 k 大 / 第 k 小元素推荐数据结构合集 - 快速排序(算法过程, 效率分析, 稳定性分析)_哔哩哔哩_bilibiliint quickselect(int[] nums, int l, int r, int k) { if (l r) return nums[k]; //找到目标递归终止 // 基准 指针 指针 int x nums[l], i l - 1, j r 1; while (i j) { do i; while (nums[i] x); //注意区分while{...} do j--; while (nums[j] x); //分别找到一个符合要求的 再向右/左移动 if (i j){ int tmp nums[i]; nums[i] nums[j]; nums[j] tmp; } } if (k j) return quickselect(nums, l, j, k); else return quickselect(nums, j 1, r, k); //分成了两个数组分别递归 }l就是视频中的中轴pivot的下标注意不是pivot本身就是随便取一个数当pivot取到了l这个位置的数字l当前处理区间左边界下标r当前处理区间右边界下标k目标下标我们要找的是数组排序后下标为k的元素难点1.思考nums[k]的含义即思考此排序是从小到大排的还是从大到小2.理解下面代码do i; while (nums[i] x); do j--; while (nums[j] x);只要当前元素比基准 x 小i 就一直右移遇到≥x 的就停。只要当前元素比基准 x 大j 就一直左移遇到≤x 的就停。3.遇到之后执行的下面代码啥意思if (i j){ int tmp nums[i]; nums[i] nums[j]; nums[j] tmp; }i找到一个大于等于基准 x的数j找到一个小于等于基准 x的数。如果iji 还在 j 左边说明这两个数站错队了把它们互相交换。相当于前面都比较符合预期不用自己调整就是符合排序的现在遇到了不符合预期了才真正需要调整了4.下面咋理解if (k j) return quickselect(nums, l, j, k); else return quickselect(nums, j 1, r, k);怎么就已经分成两段了因为在上面while循环执行过后i应该是 ≥ j 的所以就依此划分0-j段递归i-结尾段递归注意上面一部分代码可不是两段分别递归了而是分段后看k在哪一段就哪一段递归另一段直接舍弃了因为根本没必要但是如果需要完整排序的话可以另外写完整排序的代码这里不适配5.为啥是j1为啥不能写成i或者写成i 和 i-1这两种情况都直接报错还不是普通的不全面仅仅j1写成iStackOverflowError栈溢出j1写成i且 j写成i-1StackOverflowError栈溢出弄不明白了豆包讲吧https://www.doubao.com/thread/x1tgmG6JTS16FKK5P