快速排序，霍尔分区算法，使用随机主元

Question

除下面提到的方法外，有没有更好的使用随机主元进行快速排序的方法（必须使用交换）？请给予建议。

int hoare_par (int *a, int b, int e)
{
    if (b < e) {
        int p_i = __random(b, e);
        __swap(&a[b], &a[p_i])

        int p = a[b];
        b = b - 1;
        e = e + 1;

        while (1) {
            do { ++b;} while (a[b] < p);
            do { --e;} while (a[e] > p);
            if (b < e)
                 __swap( &a[b], &a[e]);
            else
                 return e;
        }
    }
    return e;
}

另外，请告知我是否存在错误。谢谢！

- codey modey

---

不想失礼，但如果你没有对快速排序进行研究，也没有测试你的代码的正确性，我们为什么要关心呢？ - Logman

我在我的端上进行了测试，也做了研究。但是，以上的实现可能不如你的正确，而且我的研究可能也不如你的好。 - codey modey

我指的是“另外，请让我知道是否不正确。”但如果你做了研究，那对我来说也没问题。无论如何，我想不出比你的更好的解决方案了。 - Logman

Answer 1

如果您查看维基百科的文章并研究那里给出的Hoare分区的伪代码，您会发现所有分区方案关心的只是所选中的枢轴在范围内（它作为一个标记来避免两个索引都超出范围）。因此，您可以随机选择范围内的任何元素作为枢轴元素，并按照那里写下的方式进行分区。

- vonbrand