0

出于某种原因，我花了一段时间才弄清楚这个问题，但有一点我仍然不确定。

在下面的代码中，这个位：

 a.at(first) = a.at(last);
 a.at(last) = a.at(++first);
 a.at(first) = pivot;

我的问题是，当 a.at(++first) 与 a.at(last) 交换时，它没有被比较过，是吗？a.at(last) 低于枢轴，因此正在移动，但是无法知道 a.at(++first) 是否大于或等于枢轴，是吗？还是我错过了什么？

#include <iostream>
#include <vector>

using namespace std;

void quick(vector<int>&);
void quick_helper(vector<int>&, int, int);  
void print(vector<int>);

int main(){

    vector<int>v(10);
    v.at(0) = 8;
    v.at(1) = 3;
    v.at(2) = 7;
    v.at(3) = 2;
    v.at(4) = 5;
    v.at(5) = 9;
    v.at(6) = 1;
    v.at(7) = 4;
    v.at(8) = 0;
    v.at(9) = 6;

    cout << "Before sorting:\n";
    print(v);
    quick (v);
    cout << "After sorting:\n";
    print(v);

    return 0;
}
void print(vector<int> a)
{  
   for (int i = 0; i < static_cast<int>(a.size()); i++)
      cout << a[i] << " ";
   cout << "\n";
}
void quick(vector<int>& a){ 
    quick_helper(a, 0, static_cast<int>(a.size() - 1));
}
void quick_helper(vector<int>& a, int l, int r){
    int i, first, last, pivot;

    if (r>l){
        first = l;
        last = r;
        i = (l+r)/2; 
        pivot = a.at(i);
        a.at(i) = a.at(first);
        a.at(first) = pivot;

        while (last > first){
            if (a.at(last) >= pivot){
                last--;
            } else {
                a.at(first) = a.at(last);
                a.at(last) = a.at(++first);
                a.at(first) = pivot;
            }
        }

        pivot = first;
        quick_helper(a, l, pivot-1);
        quick_helper(a, pivot+1, r);
    }
    return;
}
4

1 回答 1

0

没有办法知道 a.at(++first) 是否大于或等于 pivot

是的，你是对的，a.at(++first)只是一个未知的值，它取代了交换的值。它将在下一次 while 循环迭代中进行比较if (a.at(last) >= pivot) last--。

它之所以有效，是因为您的支点始终位于第一位置。

于 2013-08-17T23:12:26.970 回答