第12题-无处不在的排序算法

面试题目(常考题型)

描述

设数组 A[0..N-1] 存在 N 个无序整数，找到数组 A 中的第 K（1≤K≤N） 大数。

注意：结果是顺序排序后的第 K 个最大的元素，而不是第 K 个不同的最大元素。

示例

输入：A=[3, 7, 1, 6, 9, 1, 2], K=4

输出：6

答案解析

这道题目实际就是数组排序的变种。只要将数组排序好，就能找到对应的值。下面列出能想到的一些方案：

1. Array.prototype.sort()

利用 JavaScript 标准库中提供的 sort()方法，对数组元素进行从大到小排序。

由于不同的 JavaScript 引擎对 sort() 方法的具体实现不同，因此无法保证排序的时间和空间复杂度。

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

2. 选择排序

利用我们生活中最直观的查找方式：每次从数组剩余元素中找到最大的元素，并将其从数组中剔除，直至进行到第 K 次操作。时间复杂度为 O(n^2)。

let i = 0
while (i <= k) {
  if (!nums.length) break
  let j = 0
  for (let index = 0; index < nums.length; index++) {
    if (nums[index] > nums[j]) {
      j = index
    }
  }
  if (i === k - 1) return nums[j]
  nums.splice(j, 1)
  i += 1
}

这与选择排序原理非常相似，不同之处在于，选择排序过程中没有将每次查找到的最大元素从数组中剔除，而是把它添加到已排序序列 A[0..i-1] 的末尾。

for (let i = 0; i < nums.length - 1; i++) {
  let max = i
  for (let j = i + 1; j < nums.length; j++) {
    if (nums[j] > nums[max]) {
      max = j
    }
  }
  [nums[i], nums[max]] = [nums[max], nums[i]]
}

3. 快速排序

以下这种快速排序的写法，是从 Free Pascal 的 Demo 目录文件中学到的，也一直沿用至今。
平均时间复杂度为 O(nlogn)，为了避免快速排序退化至 O(n^2)，采用了随机化划分基准。

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat([pivot], quickSort(right));
};

---

扫一扫 关注我的公众号【前端名狮】，更多精彩内容陪伴你！

【前端名狮】