c++ - 用 vector 快速排序奇怪的错误

Question

嗨，我在为硬件编写这个函数时需要帮助。它不工作，即使它适用于数组而不是 vector 。有人可以帮忙吗？提前致谢:]。

void quick2 (vector <int> & qlist2, int left, int right) {
    int i = left, j = right;
    int middle = qlist2[qlist2.size()/2];
    if (j - i < 1) {
        return;
    }
    while (i <= j) {
        while (qlist2[i] < middle) {
            i++;
        }
        while (qlist2[j] > middle) {
            j--;
        }
        if (i <= j) {
            swap (qlist2[i], qlist2[j]);
            i++;
            j--;
        }
    }

    if (left < j)
        quick2 (qlist2, left, j);
    if (i < right)
        quick2 (qlist2, i, right);
}

Answer 1

尝试将您的函数声明为:

void quick2(vector<int> & qlist2, int left, int right)

并省略 return 语句。

问题是在 C 和 C++ 中数组是通过指针传递的。每个递归调用都会收到指向同一内存块的指针拷贝并修改同一数组，从而允许调用者看到递归调用对数组所做的修改。

vector 是对象，因此每次递归调用都会传递 vector 的完整拷贝。调用者看不到递归调用所做的任何修改。上面的更改将 引用 传递给 vector ，这样就不会为每个新函数调用复制它。相反，所有调用都对同一个对象进行操作。

此外，请检查您对middle 的初始化。如所写，您将获取数组的中间元素，该元素在每次调用中都是相同的。 (请记住，qlist2.size() 不会因调用而改变)。