1

我正在尝试为 C++ 编写此算法，但是当我尝试运行它时，什么也没有出现。我已经从问题的角度查看了所有内容，但我找不到。我已经一年没有编程了，所以我要重新开始工作。任何帮助将不胜感激，谢谢。

#include <iostream>

using namespace std;

void quickSort(int A[], int p, int r);
int partition(int A[], int p, int r);

int main(void)
{
    int elements = 8; 
    int number[8] = { 2, 8, 7, 1, 3, 5, 6, 4 };

    int first = 0;
    int last = elements - 1;

    quickSort(number, first, last);

    cout << "Sorted elements: ";

    for (int i = 0; i < elements; i++)
    {
        cout << number[i] << " ";
    }

    cout << endl;

    return 0;

}

void quickSort(int A[], int p, int r)
{
    if (p < r)
    {
        int q= 0;
        q = partition(A, p, r);
        quickSort(A, p, q - 1);
        quickSort(A, q + 1, r);
    }
}

int partition(int A[], int p, int r)
{
    int temp;

    int x = A[r];
    int i = p - 1;
    for (int j = 0; j < r - 1; j++)
    {
        if (A[j] <= x)
        {
            i++;
            temp = A[j];
            A[j] = A[i];
            A[i] = temp;
        }
    }

    temp = A[r];
    A[r] = A[i + 1];
    A[i + 1] = temp;

    return (i+1);
}
4

3 回答 3

1

我已经快速测试了你的程序，对于这个输入，这个版本给了我正确的输出：

int partition(int A[], int p, int r)
{
    int temp;

    int x = A[r];
    int i = p - 1;
    for (int j = p; j < r; j++)
    {
        if (A[j] <= x)
        {
            i++;
            temp = A[j];
            A[j] = A[i];
            A[i] = temp;
        }
    }

    temp = A[r];
    A[r] = A[i + 1];
    A[i + 1] = temp;

    return (i+1);
}

变化在于循环限制。

于 2013-11-10T22:08:28.110 回答
1

分区函数内的循环条件应为：

for (int j = p; j <= r-1; j++)

那应该解决它。

于 2013-11-10T22:11:27.353 回答
1

您的代码陷入无限递归并消耗内存，直到调用未定义的行为。因此它可能会停止执行并且不打印任何内容。

您的partition函数有严重问题，虽然我无法找出您的逻辑，但您应该使用调试器来捕获问题。检查你的i和j变量。例如，这个快速修复产生了一些正确的输出：

for (int j = i+1; j < r ; j++)
             ^^^      ^

输出：

排序的元素：1 2 3 4 5 6 7 8

我不确定它是否适用于任何大小的数据。实时代码。

于 2013-11-10T22:11:33.667 回答