快速排序找出第K大的元素

有序数组里第 K 大的元素就是index 为 array.length - k 的元素。
快速排序的思路主要就是选一个基准值p，然后将小于p的值放在p的左右，大于p的值放在p的右边，然后对左右数组进行递归。
利用这个思路，当我们找到这个基准值对应的 index，等于我们要找的index时，就可以了，不用管左右两边是否是有序的。

先看未优化版。这里是新建数组分别用来存比基准值小和大的元素

function findKthLargest(input, k) {
  const len = input.length;
  if (len < 2) return input;
  let nums = input.concat([]);

  const getQuickSortIndex = (startIndex, endIndex) => {
    const len = endIndex - startIndex + 1;
    const pivotIndex = (len >>> 1) + startIndex;
    const pivotValue = nums[pivotIndex];
    const leftArr = [];
    const rightArr = [];
    for (let i = startIndex; i <= endIndex; i++) {
      if (i === pivotIndex) continue; //不把基准值独立出来，会造成无限递归
      if (nums[i] <= pivotValue) {
        leftArr.push(nums[i]);
      } else {
        rightArr.push(nums[i]);
      }
    }
    nums.splice(startIndex,len,...[...leftArr, pivotValue, ...rightArr]) ;
    return startIndex + leftArr.length;
  };

  let targetIndex = nums.length - k;
  let start = 0,
    end = nums.length - 1;
  let index = getQuickSortIndex(start, end);
  while (index != targetIndex) {
    if (index > targetIndex) {
      end = index - 1;
    } else {
      start = index + 1;
    }
    index = getQuickSortIndex(start, end);
  }
  return nums[index];
}

然后看优化版，不新建数组，直接在原数组上操作

function getQuickSortIndex(arr, startIndex, endIndex) {
  let pivot = arr[startIndex];
  let prev = startIndex;
  for (let i = startIndex + 1; i <= endIndex; i++) {
    if (arr[i] < pivot) {
      prev++;
      [arr[prev], arr[i]] = [arr[i], arr[prev]];
    }
  }
  arr[startIndex] = arr[prev];
  arr[prev] = pivot;
  return prev;
}

function findKthLargest_1(nums, k) {
  const len = nums.length;
  if (len < 2) return nums;

  let targetIndex = nums.length - k;
  let start = 0,
    end = nums.length - 1;
  let index = getQuickSortIndex(nums, start, end);
  while (index != targetIndex) {
    if (index > targetIndex) {
      end = index - 1;
    } else {
      start = index + 1;
    }
    index = getQuickSortIndex(nums, start, end);
  }
  return nums[index];
}