0

我正在尝试编写一个快速排序函数来对 10 到 1,000,000 个数字之间的任何地方进行排序。它遍历所有内容但不排序，只是按原样打印向量。

while由于某种原因，它过早地跳出了循环。我正在使用的测试输入是：（3 6 2 5 1 7 9 10 4 8）。它的输出： (1 2 6 5 3 7 9 10 4 8)

int main()
{
    std::cout << "Which file would you like to sort?\n";
    std::cin >> file;

    std::ifstream in(file.c_str());

    // Read all the ints from in:
    std::copy(std::istream_iterator<int>(in), std::istream_iterator<int>(),
            std::back_inserter(numbers));

    int max = numbers.size();
    quickSort(numbers, 0, max-1);

    // Print the vector with tab separators:
    std::copy(numbers.begin(), numbers.end(),
            std::ostream_iterator<int>(std::cout, "\t"));
    std::cout << std::endl;

    return 0;
}


void quickSort(vector<int> &numbers, int start, int end)
{
    int i = start;
    int j = end;
    int pivot=numbers[start];
    int temp;
    while( i != j )
    {
        while( numbers[i] < pivot && i < j)
            i++;
        while( numbers[j] >= pivot && i < j)
            j--;

        temp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = temp;

        if( j < start )
        {
            quickSort( numbers, start, j );
        }

        if( i < start )
        {
            quickSort( numbers, i, end);
        }
    }
    return;
}
4

2 回答 2

3

这条线看起来不合适：

int pivot=numbers.size()/2;

numbers无论start和end位置如何，您都在选择向量的中间元素作为枢轴。

于 2012-06-26T23:57:22.490 回答
2

可能除其他外，当您移动索引以查找交换时，您实际上并没有查看向量的内容。本节：

    while( i < pivot && i < j)
        i++;
    while( j >= pivot && i < j)
        j--;

应该改成这样：

    while( numbers[i] < pivot && i < j)
        i++;
    while( numbers[j] >= pivot && i < j)
        j--;

正如其中一位评论者所提到的，更大的教训是学会使用一个好的调试器来单步调试你的代码。

同样，您应该选择枢轴作为数组值。例如pivot = numbers[start]

于 2012-06-27T00:03:36.337 回答