c++ - 我的快速选择算法没有返回正确的值

Question

所以我试图在 C++ 中实现一个快速选择算法，以便在 vector 中找到中值，但是它没有正确地对列表进行部分排序，也没有返回正确的中值。

我好像找不到哪里出错了。我是这个算法的新手，这是我第一次尝试实现它。我在下面包含了我的代码，所以如果任何比我更博学的人知道出了什么问题，我将非常感谢你的意见。

//Returns the index of the object with the kth largest value
int QuickSelect(vector<Object *> & list, int left, int right, int k){

    /*-Base case-*/
    if(left == right) /*List only contains a single element*/
        return left; /*Return that index*/

    int pivotIndex = left + (rand() % (int)(right - left + 1));
    int pivotNewIndex = Partition(list, level, left, right, pivotIndex);
    int pivotDist = pivotNewIndex - left + 1;

    if(pivotDist == k)
        return pivotNewIndex;
    else if (k < pivotDist)
        return QuickSelect(list, level, left, pivotNewIndex-1, k);
    else
        return QuickSelect(list, level, pivotNewIndex+1, right, k-pivotDist);
}


int Partition(vector<Object *> & list, int left, int right, int pivotIndex){

    int pivotValue = list.at(pivotIndex)->value;
    std::swap(list[pivotIndex], list[right]);
    int storeIndex = left;
    for(int i = left; i < right; i++){
        if(list.at(i)->value < pivotValue){
            std::swap(list[storeIndex], list[i]);
            storeIndex++;
        }
    }
    std::swap(list[right], list[storeIndex]);
    return storeIndex;
}

Answer 1

int pivotDist = pivotNewIndex - left + 1;

应该是

int pivotDist = pivotNewIndex - left;

还有

return QuickSelect(list, pivotNewIndex+1, right, k-pivotDist);

应该是

return QuickSelect(list, pivotNewIndex+1, right, k-pivotDist-1);

我的测试代码是:

int main() {
  int d[] = {0, 1, 2, 3, 4};

  do {
    std::vector<Object*> v;
    v.push_back(new Object(d[0]));
    v.push_back(new Object(d[1]));
    v.push_back(new Object(d[2]));
    v.push_back(new Object(d[3]));
    v.push_back(new Object(d[4]));

    for (int i = 0; i < v.size(); ++i) {
      std::cout << v[i]->value << " "; }
    std::cout << std::endl;

    int n = QuickSelect(v, 0, 4, 2);

    if (v[n]->value != 2) {
      std::cout << "error: ";
      for (int i = 0; i < v.size(); ++i) {
        std::cout << v[i]->value << " "; }
      std::cout << std::endl;
    }
  }
  while (std::next_permutation(&d[0], &d[sizeof(d)/sizeof(int)]));
}