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

我不确定我做错了什么。感谢您的帮助。

Answer 1

在你的分区函数的倒数第二行你应该有：

  a[r] = tmp;

而不是：

  a[r] = a[tmp];

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

C++ 快速排序算法

C++ Quicksort Algorithm

c++

algorithm

quicksort