快速选择中的分区

Question

我必须实现一个返回数组中位数的算法。因此，我选择实现Quickselect似乎很有效，并且看到三方可以使用Quicksort中使用的相同分区算法。

我的讲义中（使用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

对于快速选择，您需要使用一个递归算法，该算法将找到枢轴元素的正确位置，从而将整个数组分成两半[枢轴位置右侧的元素的值小于枢轴，而左侧的元素的值小于枢轴。枢轴位置的值大于枢轴的值]

您的算法不考虑第一个循环结束后应该做什么。它只能找到第一个选定的枢轴元素的位置（太错误了）。如果找到的枢轴位置不是中间位置（选定的枢轴不是中间值），将会发生什么？

然后应移动到左侧（如果新找到的枢轴元素位置大于中间位置），否则应移动到右侧，并再次执行上述步骤。

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

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