c++ - 使用类在 C++ 中快速排序错误

Question

我用 C++ 编写了一个程序，使用类和对象进行快速排序。我在在线编译器上编译了这个，发现它超时了，因为这段代码占用了太多时间和内存。

当我后来在 Visual C++ 2010 上编译它时，它说 unhandled exception : stack overflow我试图找出在类成员函数 void quick sort (a[],l,r) 处运行的无限循环。请帮忙。

#include <iostream>
using namespace std;

class sort;

int main()
{
    class sort
    {
    public:
        int split(int a[],int l,int r)
        {
            int i,j,p,t;
            p=a[l];
            i=(l+1);
            j=r;

            while (l<=r)
            {
                while ((a[i]<p)&&(i<j))
                    r--;

                while ((a[j]>p)&&(l<r))
                    l++;

                if (i<=j)
                {
                    t=a[i];
                    a[i]=a[j];
                    a[j]=t;
                }
            }
            t=p;
            p=a[j];
            a[j]=p;

            return j;
        }


        void quicksort(int a[],int l,int r)
        {
            int s;
            if (l<r)
            {
                s=split(a,l,r);
                quicksort(a,l,(s-1));
                quicksort(a,(s+1),l);
            }
        }

    } obj1;

    int a[30],n,i;

    cout<<"\nEnter no of elements :\t 5";
    n=5;

    cout<<"\nEnter elements :\n";
    a[0]=9;
    a[1]=6;
    a[2]=3;
    a[3]=5;
    a[4]=1;

    cout<<"\nElemets before sort :\n";
    for(i=0;i<n;i++)
        cout<<" "<<a[i];

    obj1.quicksort(a,0,(n-1));

    cout<<"\nElements after sort:\n";
    for (i=0;i<n;i++)
        cout<<" "<<a[i];

    return 0;
}

Answer 1

这里有几个问题:

int split(int a[],int l,int r)
{
    int i,j,p,t;
    p=a[l];
    i=(l+1);
    j=r;

    // consider what will happen for an array with just 1 or 2 elements?
    while (l<=r) // should be while i<=j;
    {
        while ((a[i]<p)&&(i<j))
            r--; //should be j--

        while ((a[j]>p)&&(l<r))
            l++; // should be i++

        if (i<=j) // sadly this will only true when you've got an array with 1 element 
        {
            t=a[i];
            a[i]=a[j];
            a[j]=t;
        }
    }
    t=p;
    p=a[j];
    a[j]=p;

    return j;
}

关键问题是这里的快速排序算法不正确。它的工作原理如下:

0. make i = l+1 and j = r;

1. while true:

1.1 while a[i]<a[l] i++

1.2 while a[j]>a[l]  j--

1.3 break if i>= j;

1.4 exchange a[i] and a[j]

2. exchange a[l] and a[j]

您在实现过程中做了不同的事情。