c - 以两种方式实现快速排序算法但只接受一种？

Question

我用两种方式实现了快速排序算法。

quick_sort 函数是一样的:

void quick_sort(int *a, int left, int right) {
    if (left < right) {
        int mid = partition(a, left, right);
        quick_sort(a, left, mid - 1);
        quick_sort(a, mid + 1, right);
}

partition 函数在两个实现中是不同的:

第一种方法基于 Robert Sedgewick 的“算法”一书:

int random = rand() % (right - left + 1) + left;
exchange(&a[left], &a[random]);

int i = left;
int j = right + 1;
int pivot = a[left];

while (1) {
    while (a[++i] < pivot)
        if (i == right) break;
    while (a[--j] > pivot)
        if (j == left) break;

    if (i >= j) break;

    exchange(&a[i], &a[j]);
}

exchange(&a[left], &a[j]);

return j;

第二种方式基于《算法导论》一书，这种方式比第一种方式更容易理解:

int random = rand() % (right - left + 1) + left;
exchange(&a[right], &a[random]);

int pivot = a[right];
int j = left - 1;

int i;
for (i = left; i < right; i++) {
    if (a[i] <= pivot) {
        j++;
        exchange(&a[j], &a[i]);
    }
}

exchange(&a[j + 1], &a[right]);

return j + 1;

我已经在 Online Judge Site 上提交了两个实现:TSORT , 但只接受了第一个实现，第二个是 Time Limit Exceed 。存在细微差别，但我找不到导致性能差距的原因，有人可以找到并解释一下吗？

Answer 1

您的第一个是 Hoare 分区方案，而第二个是 Lomuto 分区方案。根据多个消息来源，Lomuto 的变体不应该在实践中使用，它的唯一优势是教学，因为它更容易理解。

一些这样的来源:

1. https://en.wikipedia.org/wiki/Quicksort

   Hoare scheme is more efficient than Lomuto's partition scheme because it does three times fewer swaps on average and creates efficient partitions even when all values are equal.

2. https://cs.stackexchange.com/questions/11458/quicksort-partitioning-hoare-vs-lomuto

   Lomuto's method is simple and easier to implement, but should not be used for implementing a library sorting method.