我正在研究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];

您正在用其他成员覆盖阵列的某些部分,而不是完成交换的第三步.