快速选择(Quick-Select)的 javascript 实现。

# 快速选择

# 问题

  • 输入:n 个数的一个序列<a1, a2, ..., an>
  • 输出:找到第 k 个最小数字的元素

# 快速选择

快速选择(Quickselect)是一种从无序列表找到第 k 小元素的选择算法。它从原理上来说与快速排序有关。

快速选择的总体思路与快速排序一致,选择一个元素作为基准来对元素进行分区,将小于和大于基准的元素分在基准左边和右边的两个区域。不同的是,快速选择并不递归访问双边,而是只递归进入一边的元素中继续寻找。这降低了平均时间复杂度,从O(n log n)O(n),不过最坏情况仍然是O(n2)

与快速排序一样,快速选择一般是以原地算法的方式实现,除了选出第 k 小的元素,数据也得到了部分地排序。

# 思路

  1. 从数列中挑出一个元素,称为"基准"(pivot)。
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。
  3. 判断第 k 个最小元素位于左侧还是右侧,然后对该侧进行递归。

# js 基本思路实现

// 交换数组值
function swap(arr, a, b) {
  if (a == b) {
    return;
  }
  var c = arr[a];
  arr[a] = arr[b];
  arr[b] = c;
}

function quickSelect(iArr, start, end, k) {
  var n = end - start;
  // 若只有一个或者没有,则返回
  if (n <= 1) {
    return iArr[start];
  }
  // 若有多个,则选择基准进行位置调整,递归处理
  else {
    var p = end - 1; // 选取最后一个作为基准
    var pivot = iArr[p]; // 获取基准值
    var leftIndex = start; // 记录左侧列表位置
    for (var i = 0; i < n - 1; i++) {
      arrVal = iArr[start + i];
      // 若小于基准,则排列在左侧
      if (arrVal <= pivot) {
        swap(iArr, leftIndex++, start + i);
      }
      // 若大于基准,继续
    }
    // 交换基准至中间
    swap(iArr, leftIndex, p);
    if (leftIndex > k - 1) {
      // 若k < 基准位置,递归排序左侧
      return quickSelect(iArr, start, leftIndex, k);
    } else if (leftIndex < k - 1) {
      // 若k > 基准位置,递归排序右侧
      return quickSelect(iArr, leftIndex + 1, end, k);
    } else {
      // 若k = 基准位置,返回
      return iArr[k - 1];
    }
  }
}
部分文章中使用了一些网站的截图,如果涉及侵权,请告诉我删一下谢谢~
温馨提示喵