C++ 快速排序算法

Question

我正在使用c++实现快速排序算法，但是我一直无法使它按照预期工作。我已经查阅了多个资料，我的代码看起来毫无问题，但数组并没有像应该排序那样进行排序。

以下是我的代码：

#include <iostream>
using namespace std;

void quicksort(int[],int, int);
int partition(int[], int, int);

int main()
{
    int a[] = {5, 1, 9, 3, 8, 4, 1, 2, 6, 7};
    for (int i = 0; i < 10; i++)
    { 
        cout << a[i] << " ";
    }
    cout << endl;
    quicksort(a, 0, 9);
    for (int i = 0; i < 10; i++)
    {
            cout << a[i] << " ";
    }
    return 0;
}

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

int partition(int a[], int p, int r)
{
    int x = a[r];
    int i = (p - 1);
    for (int j = p; j <= r-1; j++)
    {
        if (a[j] <= x)
        {
                i++;
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
        }
     }
     int tmp = a[i+1];
     a[i+1] = a[r];
     a[r] = a[tmp];
     return (i + 1);
}

当我运行这段代码时，会显示以下内容：

5 1 9 3 8 4 1 2 6 7
1 1 2 4 4 4 6 7 7 7

我不确定我在这里做错了什么。谢谢你的帮助。

- tfreiner

---

你试过使用调试器逐步执行程序吗？这应该能帮助你看清发生了什么。 - LiMuBei

另外，显然：std::sort。 - Alan Stokes

另一个好的规则是，当您使用数组索引时，请尝试在for循环中始终使用“<”和上限一致的结尾索引。混合使用“最后使用的”、“最后一个之后”、“<”和“<=”的上限会令人困惑（显然也包括您自己...）。例如，如果您有一个包含5个元素的数组，请像这样编写for循环：*for (i = 0; i <5; i++)*。 - tofro

a[tmp]; 是你的主要错误。 - Jeffrey

@Tuffwer 是的，你说得对。 - Alan Stokes

Answer 1

在您的分区函数的倒数第二行，应该是这样的：

  a[r] = tmp;

改为：

  a[r] = a[tmp];

你正在用其他成员覆盖你的数组部分，而不是完成交换的第三步。

- Tuffwer

---

好的发现！然而，在更改后，我的程序显示：排序后数组的输出为8 2 8 8 32767 9 32767 100001 7。 - tfreiner

@tfreiner 我不确定。当我在 ideone 上运行你的代码时（一个在线编译器），它似乎工作正常。 - Tuffwer

@tfreiner 如果你继续遇到问题，那么你得到的值表明某些地方没有被正确初始化，或者你正在读取数组的越界但仍然在程序所拥有的内存范围内（因此没有segfault）。我建议按照tofro的建议使用调试器逐步查看程序执行时值的变化。如果你不知道如何使用调试器，也可以编写描述性的打印语句，但最好学习如何使用调试器。 - Tuffwer

我想通了，我犯了一个愚蠢的错误。我把你的编辑应用到了错误的文件上。现在它完美运行了，谢谢！ - tfreiner