STATUS_ACCESS_VIOLATION 三向快速排序 (C++)

Question

我尝试用 C++ 实现 3 路快速排序算法，如 here 所述。不幸的是我得到了例外 STATUS_ACCESS_VIOLATION.

template<typename T, size_t SIZE>
void qsort(std::array<T, SIZE> &a, std::size_t lo, std::size_t hi) {

    if (hi <= lo) {
        return;
    }

    std::size_t lt = lo, gt = hi;
    T v = a[lo];
    std::size_t i = lo;

    while (i <= gt) {
        if (a[i] < v) {
            std::swap(a[lt++], a[i++]);
        } else if (a[i] > v) {
            std::swap(a[i], a[gt--]);
        } else {
            i++;
        }
    }

    qsort(a, lo, lt - 1);
    qsort(a, gt + 1, hi);
}

template<typename T, size_t SIZE>
void quickSortThreeWay(std::array<T, SIZE> &a) {
    std::size_t arraySize = sizeof(a) / sizeof(a[0]);
    qsort(a, 0, arraySize - 1);
}

数组是一个std::array我填充了随机值。这适用于其他算法。

你能帮我找出问题所在吗？谢谢

谢谢。

Answer 1

在这行代码：

qsort(a, lo, lt - 1);

当lo为0时，lt可以为-1。不幸的是，您的签名不允许负数，因为您使用的是 size_t，所以在我的测试中，当 lo 为 0 时，lt - 1 为 18446744073709551615。此测试无法执行您想要的操作：

if (hi <= lo) { return }

然后一味地继续下去就崩溃了。你可能会想在你的方法签名中允许负数而不是 size_t，例如：

void qsort(std::array<T, SIZE> &a, int lo, int hi) {
    std::cout << "qsort (a, " << lo << ", " << hi << ")" << std::endl;

当我运行上面针对三个字符串的数组修改签名时：

std::array<std::string, 3> a;
a[0] = "hello";
a[1] = "abacus";
a[2] = "goodbye";
quickSortThreeWay (a);

最后一个参数我得到 -1:

qsort (a, 0, 2)
qsort (a, 0, 1)
qsort (a, 0, -1)
qsort (a, 1, 1)
qsort (a, 3, 2)

STATUS_ACCESS_VIOLATION 三向快速排序 (C++)

STATUS_ACCESS_VIOLATION at 3-way quicksort (C++)

c++

exception

quicksort