Quickselect中的分区

Question

我必须实现一个返回数组中值的算法。因此，我选择实现Quickselect，这似乎是有效的，我看到，对于三分区，我可以使用同样的分区算法使用在快速排序。

在我的课堂讲稿(用C代码)中报告的分区算法如下：

for (i = lo, j = hi;
     (i <= j);)
{
    while (a[i] < pivot)
    {
        i++;
    }

    while (a[j] > pivot)
    {
        j--;
    }

    if (i <= j)
    {
        if (i < j)
        {
            /* exchange values */
            tmp = a[i];  
            a[i] = a[j];
            a[j] = tmp;
        }

        i++;
        j--;
    }

}

现在，如果我的数组是:a= 40，20,100，60，80，并且我选择了数字80作为枢轴，结果是:a= 40，20， 80 ，60,100，但是正如您所看到的，正确分区中的值并不都是>80(我们有60)。如果我选择任何其他数字，该算法工作正常。

这个算法有错吗？

谢谢你提前提供帮助！

Answer 1

对于quickselect u，需要使用一种递归算法，该算法可以找到枢轴元素的正确位置，从而将整个数组分成2半，在枢轴位置右侧的元素的值小于枢轴，而位于枢轴位置左侧的元素的值大于枢轴。

您的算法没有考虑在第一个循环结束后应该做什么。它只找到第一个选择的枢轴元素的位置(这太错误了)。如果找到的枢轴位置不是中间位置(所选择的枢轴位置不是中间位置)，会发生什么情况？

然后，它应该移动到左边部分(如果新发现的枢轴元素的位置大于中间位置)，否则它应该移动到右侧，并再次执行上述步骤。

如果你什么都不懂，请发表评论

Answer 2

[40, 20, 100, 60, 80]
          i ... #while (a[i] < pivot)

[40, 20, 100, 60, 80]
          i        j ... #while (a[j] > pivot)

[40, 20, 80, 60, 100]
          i        j ... #/* exchange values */

[40, 20, 80, 60, 100]
             ij ... #i++;j--;

[40, 20, 80, 60, 100]
              j   i  ... #while (a[i] < pivot)

[40, 20, 80, 60, 100] ... exit for-loop .. finish