我quickselect算法没有返回正确的值

Question

所以我想实现在C quickselect算法++，以便找到一个向量的中值，但它是不正确的部分排序列表，也没有返回正确的中值。

我似乎无法找到错误所在。我是这个算法的新手，这是我第一次尝试实现它。以下附上我的代码，所以如果有人比我更博学有什么错误任何想法，我将非常感谢您的输入。

//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)])); 
}