我正在使用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];
您正在用其他成员覆盖阵列的某些部分,而不是完成交换的第三步。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句