c++ - C ++中的快速排序间歇性地工作

Question

我的快速排序算法有什么问题？有时它给出了正确的答案，有时它没有。这是我的代码。

#include <iomanip>
#include <iostream>
using namespace std;
void foo(int*, int, int);
int main()
{
    int* a, n;
    cin >> n;
    a = new int[n];
    srand(time(NULL));
    for (int i = 0; i <= n - 1; i++)
    {
        a[i] = rand() % 100;
        cout << setw(3) << a[i];
    }
    cout << endl;
    cout << "sorting array" << endl;
    foo(a, 0, n - 1);
    for (int i = 0; i <= n - 1; i++)
        cout << setw(3) << a[i];
    cout << endl;
    return 0;
}
void foo(int* a, int left, int right)
{
    int j = right;
    int i = left;
    int mid = (i + j) / 2;
    while (i < j)
    {
        while (a[i] < a[mid]) i++;
        while (a[j] > a[mid]) j--;
        if (i <= j)
        {
            swap(a[i], a[j]); i++; j--;
        }
    }
    if (i < right)
        foo(a, i, right);
    if (left < j) foo(a, left, j);
}   

我对我的程序做了一些更改，它开始正常工作，问题是我不明白为什么。我在下面的代码中提到了更改。所有预期的输出都与结果匹配。

#include <iomanip>
#include <iostream>
using namespace std;
void foo(int*, int, int);
int main()
{
    int* a, n;
    cin >> n;
    a = new int[n];
    srand(time(NULL));
    for (int i = 0; i <= n - 1; i++)
    {
        a[i] = rand() % 100;
        cout << setw(3) << a[i];
    }
    cout << endl;
    cout << "sorting array" << endl;
    foo(a, 0, n - 1);
    for (int i = 0; i <= n - 1; i++)
        cout << setw(3) << a[i];
    cout << endl;
    return 0;
}
void foo(int* a, int left, int right)
{
    int j = right;
    int i = left;
    int mid = (a[right] + a[left]) / 2;//CHANGED LINE from mid=(i+j)/2
    while (i < j)
    {
        while (a[i] < mid) i++; //CHANGED LINE from a[i]<a[mid]
        while (a[j] > mid) j--; //CHANGED LINE from a[j]>a[mid]
        if (i <= j)
        {
            swap(a[i], a[j]); i++; j--;
        }
    }
    if (i < right)
        foo(a, i, right);
    if (left < j) foo(a, left, j);
}

标签： c++sorting