3

假设我有一个大小为 n 的未排序数组 A。

如何在线性时间内从原始未排序列表中找到第 n/2、n/2−1、n/2+1 个最小元素？

我尝试在维基百科中使用选择算法（我正在实现基于分区的通用选择算法）。

function partition(list, left, right, pivotIndex)
 pivotValue := list[pivotIndex]
 swap list[pivotIndex] and list[right]  // Move pivot to end
 storeIndex := left
 for i from left to right-1 
     if list[i] < pivotValue
         swap list[storeIndex] and list[i]
         increment storeIndex
 swap list[right] and list[storeIndex]  // Move pivot to its final place
 return storeIndex


function select(list, left, right, k)
 if left = right // If the list contains only one element
     return list[left]  // Return that element
 select pivotIndex between left and right //What value of  pivotIndex shud i select??????????
 pivotNewIndex := partition(list, left, right, pivotIndex)
 pivotDist := pivotNewIndex - left + 1 
 // The pivot is in its final sorted position, 
 // so pivotDist reflects its 1-based position if list were sorted
 if pivotDist = k 
     return list[pivotNewIndex]
 else if k < pivotDist 
     return select(list, left, pivotNewIndex - 1, k)
 else
     return select(list, pivotNewIndex + 1, right, k - pivotDist)

但我还没有理解 3 或 4 个步骤。我有以下疑问：

  1. 我是否选择了正确的算法，它是否真的能在我的程序的线性时间内工作。我有点困惑，因为它类似于快速排序。
  2. 调用函数时从主函数中选择，左、右和k的值是多少。考虑我的数组是列表 [1...N]。
  3. 我是否必须调用 select 函数 3 次，一次查找 n/2th 最小，另一次查找 n/2+1 th 最小，再调用一次 n/2-1th 最小，还是可以一次完成打电话，如果是，怎么打？
  4. 同样在函数选择（第三步）“在左右之间选择pivotIndex”中，我应该为我的程序/目的选择什么pivotIndex 值。

谢谢！

4

1 回答 1

2

它类似于快速排序，但它是线性的，因为在快速排序中，您需要同时处理枢轴的左侧和右侧，而在快速选择中，您只处理一侧。

初始调用应该是Select(A, 0, N, (N-1)/2)如果N是奇数；N如果是偶数，你需要准确地决定你想要做什么。

要找到中位数和左/右，你可能想调用它来找到中位数，然后只做左边数组组件的最大值和右边组件的最小值，因为你知道一旦中值选择阶段完成，中值左侧的所有元素都将小于它，而右侧的所有元素将大于（或等于）。这是 O(n) + n/2 + n/2 = O(n) 总时间。

有很多方法可以选择枢轴指数。出于偶然目的，中间元素或随机索引可能就足够了。

于 2012-04-13T03:52:26.100 回答