在位随机选择算法

Question

我们目前正在研究算法，因此即使这不是作业相关任务，我也将此问题标记为“作业”。只是为了保险起见。

我们刚刚学习了随机选择算法，它的逻辑似乎很简单。从列表中选择一个元素，然后将该元素放到其正确的位置。然后在一个子列表中重复这个过程，直到索引处的元素处于其位置。其中索引是您希望在排序列表中的元素的位置。

这应该是快速排序算法的修改版本。但我们只对一个子列表进行排序，而不是两个子列表。因此可以提高性能 (在大O符号方面)。

使用外部存储器 (C++和基于零的数组)，我可以成功地实现这种算法：

int r_select2(vector<int>& list, int i)
{
   int p = list[0];

   vector<int> left, right;

   for (int k = 1; k < list.size(); ++k)
   {
      if (list[k] < p)  left.push_back(list[k]);
      else     right.push_back(list[k]);
   }

   int j = left.size();

   if (j > i) p = r_select2(left, i);
   else if (j < i) p = r_select2(right, i - j - 1);

   return p;
}

然而，我想要使用原地算法（in-situ）来实现，而不是使用额外的子数组。我相信这应该是一个容易/平凡的任务。但是，在某个地方，我的原地版本出了问题。也许只是太晚了，我需要休息，但我看不到以下版本失败的根本原因：

int r_select(vector<int>& list, int begin, int end, int i)
{
   i = i + begin;
   int p = list[begin];

   if (begin < end)
   {
      int j = begin;
      for (int k = begin + 1; k < end; ++k)
      {
         if (list[k] < p)
         {
            ++j;
            swap(list[j], list[k]);
         }
      }

      swap(list[begin], list[j]);

      if (j > i) p = r_select(list, begin, j, i);
      else if (j < i) p = r_select(list, j + 1, end, i - j);
   }

   return p;
}

在这两个例子中，第一个元素被用作枢轴以保持设计简单。在这两个例子中，i 是我想要的元素的索引。

有没有想法第二个例子是哪里出了问题？这是一个简单的偏移错误吗？

谢谢大家！

- PinkDuck

---

你能提供一些样例输入，以及对应的输出和期望输出吗？ - sarnold

输入列表可能以随机顺序包含数字0到99。在调用r_select(list, 0, list.size(), 88)后，我期望返回88。 - PinkDuck

@PinkDuck：你的实现提供了什么？一个失败的测试用例可以帮助审阅者理解错误出在哪里。 - amit

示例：list = 3, 8, 4, 6, 1, 0。调用r_select（list，0，list.size（），3）; 预期结果：4。实际结果：6。 - PinkDuck

Answer 1

这听起来有些可疑：

i = i + begin;
...
r_select(list, begin, j, i);

- maniek