无法理解快速选择算法-Java 学习之路

我在理解快速选择算法时遇到问题 . 我知道它基于快速排序算法（我很熟悉）并且它为您提供了所需的结果，可能会使数组的一部分未排序 . 现在这里是我遇到困难的地方 . 问题是从数组中找到第二个最小的元素：

int a[4] = {1,3,5,2} ;

现在假设我们正在随机选择枢轴然后根据this post我们有以下条件：

k == pivot . 然后你已经找到了最小的第k个 . 这是因为分区的工作方式 . 确切地说，k-1个元素小于第k个元素 .
k < pivot . 然后第k个最小位于枢轴的左侧 .
k > pivot . 然后第k个最小的位于枢轴的右侧 . 要找到它，你实际上必须在右边找到k-pivot最小数字 .

如果有人能解释 k==pivot 意味着我们找到了第k个（在我的情况下是第二个最小的元素），我将不胜感激 . 另外，如果我们 k < pivot ，我们是否重复了枢轴左侧的过程？

2 回答

是的，当 pivok == k 时，你在枢轴左边有 k-1 元素 smaller 而不是枢轴，所以你找到了 k-th 最小数量的数组，即枢轴，但是如果是 k < pivot ，请在数组的左侧搜索，因为数据透视 > kth最小元素，否则枢轴 < 第k个数组的最小元素，因此在右侧搜索以增加枢轴 .
来自wikipedia：

// Returns the n-th smallest element of list within left..right inclusive (i.e. n is zero-based).
  function select(list, left, right, n)
     if left = right        // If the list contains only one element
         return list[left]  // Return that element
     pivotIndex  := ...     // select a pivotIndex between left and right, e.g. left + Math.floor(Math.random() * (right - left + 1))
     pivotIndex  := partition(list, left, right, pivotIndex)
     // The pivot is in its final sorted position
     if n = pivotIndex
         return list[n]
     else if n < pivotIndex
         return select(list, left, pivotIndex - 1, n)
     else
         return select(list, pivotIndex + 1, right, n)

希望这可以帮助！

回复于 2024-04-24T14:07:23+08:00

2

如果k = pivot，你将在pivot的左边有k-1个项目 . 由于分区，每个都小于枢轴项 . 此外，由于分区，右侧的每个项目都大于枢轴项目 . 因此，枢轴项必须是第k个最大的 . 说得通？

回复于 2024-04-24T14:07:23+08:00

无法理解快速选择算法

2 回答

相关问题