一次递归调用快速排序

Question

我们所有人都知道如何使用两个或多个递归调用来编写快速排序。

前几天老师说递归调用一次就可以搞定。实际上我不知道如何只用一个递归调用来保存 O(n log n)。

有什么想法吗？

Answer 1

示例 C++ 快速排序，每次迭代一次递归调用，以将堆栈开销减少到 O(log(n))。还使用 3 的中位数作为主元，并排除分区的中间值 == 主元。

void QuickSort(int a[], size_t lo, size_t hi) {
    while(lo < hi){
        size_t i = lo, j = (lo+hi)/2, k = hi;
        int p;
        if (a[k] < a[i])            // median of 3
            std::swap(a[k], a[i]);
        if (a[j] < a[i])
            std::swap(a[j], a[i]);
        if (a[k] < a[j])
            std::swap(a[k], a[j]);
        p = a[j];
        i--;                        // Hoare partition
        k++;
        while (1) {
            while (a[++i] < p);
            while (a[--k] > p);
            if (i >= k)
                break;
            std::swap(a[i], a[k]);
        }
        i = k++;
        while(i > lo && a[i] == p)  // exclude middle values == pivot
            i--;
        while(k < hi && a[k] == p)
            k++;
        // recurse on smaller part, loop on larger part
        if((i - lo) <= (hi - k)){
            QuickSort(a, lo, i);
            lo = k;
        } else {
            QuickSort(a, k, hi);
            hi = i;
        }
    }
}

为了在代码中只有一个递归调用，最后一部分可以替换为：

        // recurse on smaller part, loop on larger part
        size_t ll, rr;
        if((i - lo) <= (hi - k)){
            ll = lo;
            rr = i;
            i = hi;
        } else {
            ll = k;
            rr = hi;
            k = lo;
        }
        QuickSort(a, ll, rr);
        lo = k;
        hi = i;
    }
}

一次递归调用快速排序

Quicksort with one recursive call

c

sorting

quicksort