尽管没有错误并完全执行，但 C++ 程序中没有输出

Question

我用 C++ 编写了以下递归程序以使用 QuickSort 算法对数组进行排序，但我没有得到任何输出（虽然我应该收到 space 分隔数组的输出，因为 cout）尽管程序正在执行。

我对 C++（不是编程）还比较陌生，无法找到任何关于我的问题的具体内容。

请帮忙！！

代码：

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int partition(int a[], int low, int high)
{
    int pivot = a[high];
    int x = low;
    int y = high;

    while (x < y)
    {
        do
        {
            x++;
        } while (a[x] <= pivot);
        do
        {
            y--;
        } while (a[y] > pivot);

        a[x] = a[x] + a[y];
        a[y] = a[x] - a[y];
        a[x] = a[x] - a[y];
    }

    a[x] = a[x] + a[high];
    a[high] = a[x] - a[high];
    a[x] = a[x] - a[high];

    return x;
}

void quickSort(int a[], int low, int high)
{
    if (low < high)
    {
        int new_limit = partition(a, low, high);
        quickSort(a, low, new_limit);
        quickSort(a, new_limit + 1, high);
    }
}

int main()
{
    int n;
    int a[1001];
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    a[0] = -1001;

    quickSort(a, 0, n);

    for (int i = 1; i <= n; ++i)
    {
        cout << a[i] << " ";
    }

    return 0;
}

放置随机 cout 语句，只有快速排序函数中递归快速排序调用之前的语句返回输出。

我的输入：

7
8 7 14 6 98 5 4

Answer 1

此代码：

    do
    {
        x++;
    } while (a[x] <= pivot);

    do
    {
        y--;
    } while (a[y] > pivot);

要去月球然后回来。您没有以任何方式检查边界。一旦您尝试使用这些索引写入数组，您就会破坏堆栈。

这个数组：

int a[1001];

未初始化。因此，它将填充未定义的数据，这可能会转换为大于 x 的整数。

最后但同样重要的是：

 quickSort(a, 0, n);

您将 n（数组的大小）作为 high 传递，但您正在使用 high 对数组进行索引。

此处：

int pivot = a[high];

这里：

a[high] = a[x] - a[high];

这也会导致您出现未定义的行为。

Answer 2

除了你提出的错误，我已经发表了评论。

#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int partition(int a[], int low, int high)
{
    int pivot = a[high];
    int x = low;
    int y = high - 1; // should be high - 1

    while (x <= y) // this must be less than or equal to account for x == y
    {
        while (x <= high - 1 && a[x] <= pivot) { // should use while loop instead of while do loop
            x++;
        }
        while (y >= low && a[y] > pivot) {
            y--;
        }
        if (x < y) { // swap only if the array has not been completely partitioned
            a[x] = a[x] + a[y]; 
            a[y] = a[x] - a[y];
            a[x] = a[x] - a[y];
        }
    }


    if (x != high){ // you must check x != high because of this obfuscated swap, think about why
        a[x] = a[x] + a[high]; 
        a[high] = a[x] - a[high];
        a[x] = a[x] - a[high];
    }

    return x;
}

void quickSort(int a[], int low, int high)
{
    if (low < high)
    {
        int new_limit = partition(a, low, high);
        quickSort(a, low, new_limit - 1); // new_limit - 1 instead of new_limit
        quickSort(a, new_limit + 1, high);
    }
}

int main()
{
    int n;
    int a[1001];
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    a[0] = -1001;

    quickSort(a, 1, n); // pass index 1 in lower bound if you want don't want to use a[0]!

    for (int i = 1; i <= n; ++i)
    {
        cout << a[i] << ' ';
    }
    return 0;
}

输入的输出：

4 5 6 7 8 14 98

尽管没有错误并完全执行，但 C++ 程序中没有输出

No output in C++ program despite no errors and complete execution

c++

sorting

recursion

quicksort