js实现快速选择排序

快速选择排序（QuickSelect）是一种基于快速排序算法的选择算法，用于从一个无序数组中选择第k小的元素。

实现步骤：

定义快速选择函数，接收一个数组和一个整数k作为参数。
首先选定一个基准元素pivot，并将数组分成左右两个部分，左边的元素小于等于pivot，右边的元素大于pivot。
如果左边的元素个数等于k-1，则返回pivot；如果左边的元素个数小于k-1，则在右边的部分继续查找第k-1-left个元素；否则在左边的部分继续查找第k小的元素。
迭代以上步骤，直到找到第k小的元素。

代码实现如下：

function quickSelect(arr, k) {
  if (k < 1 || k > arr.length) {
    return null;
  }
  
  const pivot = arr[Math.floor(Math.random() * arr.length)];
  const left = [];
  const right = [];
  const equal = [];
  
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else if (arr[i] > pivot) {
      right.push(arr[i]);
    } else {
      equal.push(arr[i]);
    }
  }
  
  if (k - 1 < left.length) {
    return quickSelect(left, k);
  } else if (k - 1 < left.length + equal.length) {
    return pivot;
  } else {
    return quickSelect(right, k - left.length - equal.length);
  }
}

测试代码如下：

const arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
console.log(quickSelect(arr, 1)); // 1
console.log(quickSelect(arr, 2)); // 1
console.log(quickSelect(arr, 3)); // 2
console.log(quickSelect(arr, 4)); // 3
console.log(quickSelect(arr, 5)); // 3
console.log(quickSelect(arr, 6)); // 4
console.log(quickSelect(arr, 7)); // 5
console.log(quickSelect(arr, 8)); // 5
console.log(quickSelect(arr, 9)); // 5
console.log(quickSelect(arr, 10)); // 6
console.log(quickSelect(arr, 11)); // 9
console.log(quickSelect(arr, 12)); // null
console.log(quickSelect(arr, 0)); // null
``