我正在使用 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
我不确定我在这里做错了什么。感谢您的帮助。
最佳答案
在你的分区函数的倒数第二行你应该有:
a[r] = tmp;
代替:
a[r] = a[tmp];
您正在用其他成员覆盖数组的一部分,而不是完成交换的第三步。
关于C++ 快速排序算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35904218/