为什么随机选择算法在 Array[low] 时返回元素(低 === 高）

Why does the Randomized-Select algorithm return the element at Array[low] when (low === high)?

本文关键字：元素 返回 算法 选择 随机 Array low 为什么      更新时间：2023-09-26

有人可以向我解释为什么算法在第 4 行**if情况为真时返回array[low]元素。如果partition从pivot+1 to high在子数组的更大一侧递归到1的长度，那么order就不存在了吗？

function randomizedSelect(array, low, high, order) {
  var pivot, count;
  if (low === high) {   **
    return array[low];  **
  }
  pivot = partition(array, low, high); 
  count = pivot - low + 1;
  if (count === order) {
    return array[pivot];
  } else if (order < count) {
    return randomizedSelect(array, low, pivot-1, order);
  } else {
    return randomizedSelect(array, pivot+1, high, order - count);
  }
}

随机选择算法所做的是从位于索引low到high之间的数组中选择一个数字。如果索引 low 和 high 之间存在超过 1 个数字，则它将跳过if condition并进入分区。但是，这里的第 4 行是边缘情况，其中低和高之间只存在一个数字，即low和high基本相同。所以，我们可以返回任何东西，即使你return array[high]，结果也会和它是一样的索引（数字）。希望这可能对您有所帮助。

相关文章：