Hot100-排序

1.快排

215. 数组中的第K个最大元素 - 力扣（LeetCode）

（1）第k大的元素在排序数组中的位置是nums.length - k。

假设我们有一个数组nums = [3, 2, 1, 5, 6, 4]，并且我们想找到第2大的元素。

步骤 1：排序数组

首先，我们对数组进行排序：

排序后的数组： [1, 2, 3, 4, 5, 6]

步骤 2：理解第k大元素的位置

在排序后的数组中，第2大的元素是5。它位于索引4的位置（从0开始计数）。

（2）快排的思路：

先分块，再递归。

快速排序算法—图文详解，一篇就够了！-CSDN博客

class Solution {//快排：/*分区，随便找一个中间值x，数组在x左边的值应该都<=x，在x右边的值应该都>=x从子数组 a[l⋯r] 中选择任意一个元素 x 作为主元，调整子数组的元素使得左边的元素都小于等于它，右边的元素都大于等于它， （递归的思想）x 的最终位置就是 第k大的元素。*//*快排：1.分区 2.递归找khttps://blog.csdn.net/qq_39181839/article/details/109478094*/public int findKthLargest(int[] nums, int k) {//第k大元素在排序数组中的位置是nums.length - kreturn quicksort(nums, 0, nums.length-1, nums.length - k);}public int quicksort(int[] nums, int left, int right, int k){//递归终止条件if (left >= right){return nums[left];}//单层递归逻辑int p = partition(nums, left, right);if ( p==k){return nums[p];}else if (p < k){//需要在右侧分区继续查找return quicksort(nums, p+1, right, k);}else {// 需要在左侧分区继续查找return quicksort(nums, left, p-1, k);}}public int partition(int[] nums, int left, int right){int base = nums[left];while(left<right){//从右往左//一步步向左移，直到找到比base小的数停下来，替换此时🐻l所在位置的元素while(left<right && base <=nums[right]){right--;}nums[left] = nums[right];//从左往右while(left<right && base >=nums[left]){left++;}nums[right] = nums[left];   }//此时🐻l、🐻r指向同一元素//base替换此元素nums[left] = base;return left;}
}