不一致的快速排序功能

Question

所以我写了这个快速排序函数，它适用于一些输入。例如，它适用于以下输入：“5 4 3 2 1”、“3 4 5 6 7”等
但是，当我输入类似：“0 3 5 4 -5 100 7777 2014”时，它总是会混淆多位数。
我希望有人可以帮助指出我的代码在这个测试用例中失败的地方。

Sort.cpp

std::vector<int> QuickSort::sortFunc(std::vector<int> vec, int left, int right) {
int i = left, j = right;
int tmp;
int pivot = vec.at( (left + right) / 2 );

/* partition */
while (i <= j) { 
    while (vec.at(i) < pivot)
        i++;
    while (vec.at(j) > pivot)
        j--;
    if (i <= j) {
        tmp = vec.at(i);
        vec.at(i) = vec.at(j);
        vec.at(j) = tmp;
        i++;
        j--;
    }
}

/* recursion */
if (left < j)
    return sortFunc( vec, left, j );
if (i < right)
    return sortFunc( vec, i, right );
else
{
    return vec;
}
}

main.cpp

 int main()
{

// The user inputs a string of numbers (e.g. "6 4 -2 88 ..etc") and those integers are then put into a vector named 'vec'.
std::vector<int> vec;

// Converts string from input into integer values, and then pushes said values into vector.
std::string line;
if ( getline(std::cin, line) )
{
    std::istringstream str(line);

    int value;
    str >> value;
    vec.push_back( value );
    while ( str >> value ) 
    {
        vec.push_back( value );
    }
}
// Creating QuickSort object.
QuickSort qSort;
QuickSort *ptrQSort = &qSort;
// Creating new vector that has been 'Quick Sorted'.
int vecSize = vec.size();
std::vector<int> qSortedVec;
qSortedVec = ptrQSort->sortFunc( vec, 0, vecSize-1 );

// Middle, start, and end positions on the vector.
int mid = ( 0 + (vec.size()-1) )  / 2;
int start = 0, end = vec.size() - 1;

// Creating RecursiveBinarySearch object.
RecursiveBinarySearch bSearch;
RecursiveBinarySearch *ptrBSearch = &bSearch;
//bool bS = ptrBSearch->binarySearch( qSortedVec, mid, start, end );
bool bS = ptrBSearch->binarySearch( bSortedVec, mid, start, end );


/*--------------------------------------OUTPUT-----------------------------------------------------------------------*/

// Print out inputted integers and the binary search result.

// Depending on the binary search, print either 'true' or 'false'.
if ( bS == 1 )
{
    std::cout << "true ";
}
if ( bS == 0 )
{
    std::cout << "false ";
}

// Prints the result of the 'quick sorted' array.
int sortedSize = qSortedVec.size();
for ( int i = 0; i < sortedSize; i++ )
{
    std::cout << qSortedVec[i] << " ";
}
std::cout << "\n";


return 0;
}

感谢你们能给我的所有帮助。

Answer 1

我不确定这是否完全解决了问题，但是在对左侧部分进行排序后，您仍然需要对右侧部分进行排序，但是您已经 return 了。

此外，按值传递矢量并 returning 它是开销并且不需要，因为最后应该只有一个版本的矢量，因此首选按引用传递。在进行递归时，有时需要按值传递和 returning，尤其是在回溯（寻找不同的路径）时，但在左右提供所需状态的情况下则不需要。

不一致的快速排序功能

Inconsistent Quick Sort Function

c++

sorting

algorithm

quicksort