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

如果您查看 Wikipedia 的文章并研究那里给出的 Hoare 分区伪代码，您会发现所有分区方案关心的是选定的枢轴是否在范围内（它充当哨兵以避免用完两个指数的范围）。因此，您可以随机选择范围内的任何元素作为枢轴元素，并按照那里写下的方式进行分区。