时间戳

首页 > 解决方案 > 递归快速排序：为什么这个分区是错误的？

c++ - 递归快速排序：为什么这个分区是错误的？

问题描述

我正在用 C++ 编写递归 3 路分区，但我看不出这里有什么问题。（97% 的时间是正确的，有时是不正确的。这让我很难调试。）

期望不变量：分区后A[p, ..., p + less1 + less2 - 1]小于pivot，A[p + less1 + less2, ..., p + less1 + less2 + same1 + same2 - 1]与pivot相同，其余大于pivot。

错误结果：“中间”部分（与枢轴值相同的部分）未正确定位。

可重现的测试用例： A = {0, 1, 4, 7, 6, 9, 3, 10, 11, 12, 2, 8, 5} p = 0, r = 12, pivot = 11

预期输出less：11

电流输出：10

代码：

template <typename T>
void PPartition(std::vector<T>& A, size_t p, size_t r, const T& pivot, std::size_t& less, std::size_t& same) {
    if (p == r) {
        less = A[p] < pivot;
        same = A[p] == pivot;
        return;
    }
    std::size_t m = (p + r) / 2;
    std::size_t less1 = 0, less2 = 0, same1 = 0, same2 = 0;
    PPartition(A, p, m, pivot, less1, same1);
    PPartition(A, m + 1, r, pivot, less2, same2);
    if (less2 > m - p + 1 - less1) {
        // sends "less" part of the right to the left
        for (std::size_t k = 0; k < m - p + 1 - less1; k++) {
            std::swap(A[p + less1 + k], A[m + less2 - k]);
        }
        // maintains "equal" part
        for (std::size_t k = 0; k < same1 + same2; k++) {
            std::swap(A[p + less1 + less2 + k], A[m + less2 + same2 - k]);
        }
    } else {
        // sends "less" part of the right to the left
        for (std::size_t k = 0; k < less2; k++) {
            std::swap(A[p + less1 + k], A[m + less2 - k]);
        }
        // maintains "equal" part
        for (std::size_t k = 0; k < same1 + same2; k++) {
            std::swap(A[p + less1 + less2 + k], A[m + less2 + same2 - k]);
        }
    }
    less = less1 + less2;
    same = same1 + same2;
}

标签： c++algorithmsortingquicksort

解决方案

自我回答：

如果less2 == 0，那么我们不应该将左侧部分的“中间”分区与右侧部分交换。

template <typename T>
void PPartition(std::vector<T>& A, size_t p, size_t r, const T& pivot, std::size_t& less, std::size_t& same) {
    if (p == r) {
        less = A[p] < pivot;
        same = A[p] == pivot;
        return;
    }
    std::size_t m = (p + r) / 2;
    std::size_t less1 = 0, less2 = 0, same1 = 0, same2 = 0;
    PPartition(A, p, m, pivot, less1, same1);
    PPartition(A, m + 1, r, pivot, less2, same2);
    if (less2 > m - p + 1 - less1) {
        for (std::size_t k = 0; k < m - p + 1 - less1; k++) {
            std::swap(A[p + less1 + k], A[m + less2 - k]);
        }
        for (std::size_t k = 0; k < same1 + same2 && p + less1 + k < m + same2 - k; k++) {
            std::swap(A[p + less1 + less2 + k], A[m + less2 + same2 - k]);
        }
    } else {
        for (std::size_t k = 0; k < less2; k++) {
            std::swap(A[p + less1 + k], A[m + less2 - k]);
        }
        if (less2 > 0) {
            for (std::size_t k = 0; k < same1 + same2; k++) {
                std::swap(A[p + less1 + less2 + k], A[m + less2 + same2 - k]);
            }
        } else {
            for (std::size_t k = 0; k < same2; k++) {
                std::swap(A[p + less1 + same1 + k], A[m + same2 - k]);
            }
        }
    }
    less = less1 + less2;
    same = same1 + same2;
}

推荐阅读