algorithm - 维基百科的quickselect代码不正确吗？

我正在维基百科上阅读QuickSelect算法：https://en.wikipedia.org/wiki/Quickselect

  function select(list, left, right, k)
     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 + floor(rand() % (right - left + 1))
     pivotIndex  := partition(list, left, right, pivotIndex)
     // The pivot is in its final sorted position
     if k = pivotIndex
         return list[k]
     else if k < pivotIndex
         return select(list, left, pivotIndex - 1, k)
     else
         return select(list, pivotIndex + 1, right, k - pivotIndex)

最后一个递归调用不正确吗？我认为最后一个参数应该是k而不是k - pivotIndex。我是不是丢了什么东西？

最佳答案

你说得对——9月20日的最后一次修正引入了这个错误。
头条评论说

// Returns the k-th smallest element of list within left..right inclusive
// (i.e. left <= k <= right).

k是在所有索引范围内定义的，它是绝对的，而不是像您在注释中注意到的那样相对于局部低边框。
Aslo检查了我的kselect实现，它在第二个调用中使用了k。

关于algorithm - 维基百科的quickselect代码不正确吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58178197/