quicksort - 快速排序，霍尔分区，使用随机枢轴

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;
}

另外，如果不正确，请告诉我。谢谢!

Answer 1

如果你看一看维基百科的 article并研究那里给出的 Hoare 分区的伪代码，您会发现所有分区方案关心的是所选枢轴位于范围内的某个位置(它作为一个哨兵，以避免用完两个索引的范围)。因此，您可以随机选择范围内的任何元素作为枢轴元素，然后按照此处的说明进行分区。