TopK问题

Sort 得2分

let findKthLargest = function(nums, k) {
nums.sort((a, b) => b - a).slice(0, k);
return nums[k-1]
}

时间复杂度:O(nlogn)

空间复杂度:O(logn)

sort方法在数组长度小于10的时候，在V8 7.0以下版本使用的是快速排序，在7.0+以上舍弃快速排序因为其不稳定，时间复杂度退化为O(n ^ 2)

冒泡排序得5分

1. 从数组的第一个元素开始，依次比较相邻的两个元素。
2. 如果前一个元素比后一个元素大，则交换它们的位置。
3. 一轮下来，最大的元素会被“冒泡”到数组的末尾。
4. 忽略末尾已经排好序的元素，重复上述过程，直到所有元素有序。

let findKthLargest = function (nums, k) {
  // 进行k轮冒泡
  bubbleSort(nums, k);
  return nums[nums.length - k];
};
let bubbleSort = function (arr, k) {
  for (let i = 0; i < k; i++) {
    // 提前退出循环的标识
    let flag = false;
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        flag = true;
        // 发生数据交换
      }
    }
    // 没有数据交换
    if (!flag) break;
  }
};
var items = [1, 9, 2, 8, 3, 7, 4, 6, 5];
console.log(findKthLargest(items, 4));

时间复杂度:O(nk)，最好O(n)

空间复杂度:O(1)

快速排序得5分

1. 选择基准（pivot）：通常选最右边元素。

   分区（partition）：

   • 将数组划分成两部分，左边都小于等于 pivot，右边都大于 pivot。
   • 同时把 pivot 放到它最终应该在的位置。

   递归排序：

   • 对基准左边的子数组递归快速排序。
   • 对基准右边的子数组递归快速排序。

function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return; // 递归终止条件

  const pivotIndex = partition(arr, left, right);
  quickSortInPlace(arr, left, pivotIndex - 1);  // 排序左半部分
  quickSortInPlace(arr, pivotIndex + 1, right); // 排序右半部分
}

function partition(arr, left, right) {
  const pivot = arr[right]; // 最右作为基准
  let i = left - 1;

  for (let j = left; j < right; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]]; // 交换小的元素到左边
    }
  }

  // 最后将 pivot 放到正确位置
  [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
  return i + 1; // 返回基准值的位置
}

平均时间复杂度：O(n log n) 因为每次划分数组大约平分，递归深度是 log n，每层处理n个元素。

最坏时间复杂度：O(n²) 当每次选的基准都是数组最大或最小元素，划分极不平衡，变成退化成冒泡排序。

空间复杂度： 快速排序的空间复杂度取决于递归深度，平均是 O(log n)，最坏是 O(n)。

堆排序得8分

不懂堆排序的先去这里看清楚原理

• 堆顶是当前最小的元素
• 每次将堆顶元素移到末尾，排在当前未排序序列的“尾部”
• 不断调整堆，直到排序完成

function heapSortDescending(arr) {
  const n = arr.length;

  // 1. 构建最小堆（从最后一个非叶子节点开始）
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    minHeapify(arr, n, i);
  }

  // 2. 取出最小元素放到数组末尾
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]]; // 将最小值放末尾
    minHeapify(arr, i, 0);               // 调整堆顶为最小堆
  }

  return arr;
}

// 最小堆调整函数
function minHeapify(arr, n, i) {
  let smallest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;

  if (left < n && arr[left] < arr[smallest]) {
    smallest = left;
  }
  if (right < n && arr[right] < arr[smallest]) {
    smallest = right;
  }

  if (smallest !== i) {
    [arr[i], arr[smallest]] = [arr[smallest], arr[i]];
    minHeapify(arr, n, smallest);
  }
}

时间复杂度:

操作	时间复杂度
建堆	O(n)
每次heapify	O(log n)
总排序过程	O(n log n)

空间复杂度:O(k)

快速选择排序得9分

• 选一个基准数 pivot（如 7）
• 把数组分成两部分：
  • 小于等于 pivot 的放左边
  • 大于 pivot 的放右边
• 然后继续递归左右两边

但我们只想找第 K 小的元素！所以只需要：

✅ 每次分区完，看 pivot 的位置是不是我们要找的第 K 个位置：

• 是 → 找到了，直接返回
• 不是 → 只往左或右继续找，不用排另一半！

这样就避免了不必要的排序。

function quickSelect(arr, k) {
  return select(arr, 0, arr.length - 1, k - 1); // 第 k 小 => 下标是 k-1
}

function select(arr, left, right, kIndex) {
  if (left === right) return arr[left];

  const pivotIndex = partition(arr, left, right);

  if (pivotIndex === kIndex) {
    return arr[pivotIndex];
  } else if (pivotIndex < kIndex) {
    return select(arr, pivotIndex + 1, right, kIndex); // 去右边找
  } else {
    return select(arr, left, pivotIndex - 1, kIndex);  // 去左边找
  }
}

// 分区函数：以 arr[right] 为 pivot，把 <=pivot 放左边，返回新 pivot 下标
function partition(arr, left, right) {
  const pivot = arr[right];
  let i = left;

  for (let j = left; j < right; j++) {
    if (arr[j] <= pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }

  [arr[i], arr[right]] = [arr[right], arr[i]]; // 把 pivot 放到正确位置
  return i;
}

时间复杂度:平均O(n)，最坏O(n^2)

空间复杂度:O(1)