如何在C++中实现快速排序算法

Question

这是MITOcw(Introduction to Algorithms )讲座中的快速排序算法

QUICKSORT(A,p,q)
if(p < q)
then r = PARTITION(A,p,q)
     QUICKSORT(A,p,r-1)
     QUICKSORT(A,r+1,q)

PARTITION(A,p,q)
x = A[p]
i=p
for j = p+1 to q
    if A[j] <= x
       then i = i+1
            swap A[i] with A[j]
swap A[p] with A[i]
return i

这里是整数数组上的C++实现

#include <iostream>

using namespace std;

void quickSort(int *,int,int);

int partition(int *, int,int);

int main()
{
    int A[10]={6,10,13,5,8,3,2,25,4,11};
    int p=0,q=10;

    cout<<"======Original======="<<endl;
    for(int f=0; f<10; f++)
        cout<<A[f]<<endl;

    quickSort(A,p,q);

    cout<<"======Sorted======="<<endl;
    for(int f=0; f<10; f++)
        cout<<A[f]<<endl;
}


void quickSort(int *A, int p,int q)
{
    int r;
    if(p<q)
    {
        r=partition(A, p,q);
        quickSort(A,p,(r-1)); //I think the problem is here this first quickSort call
                              // is reducing the value of r and hence value of q becomes
                              // less than p recursively. How can I separate both calls
                              // one for left and one for right sub array of the pivot. 
        quickSort(A,(r+1),q);
    }
}


int partition(int *A, int p,int q)
{
    int x= A[p];
    int i=p;
    int temp;
    int j;

    for(j=p+1; j<q; j++)
    {
        if(A[j]<=x)
        {
            i=i+1;
            temp= A[j];
            A[j]=A[i];
            A[i]=temp;
        }

    }

    temp= A[p];
    A[p]=A[i];
    A[i]=temp;

    return i;
}

尽管前两次运行的quickSort函数提供了所需的输出,但代码不会产生排序数组.也就是说它将第一个枢轴元素放置到正确的位置

Answer 1

你的考虑是错误的.值r不会改变,因为它是作为Quicksort函数(不是引用)的值给出的.您可以处理范围p,q例如p范围中q的第一个索引和不在范围内的第一个索引.

因此,你的电话错了:

r=partition(A, p,q);
quickSort(A,p,r); //range is from A[p] to A[r-1] 
quickSort(A,(r+1),q); //range is from A[r+1] to A[q-1]

这是完整的例子.我用std :: swap来改变元素和ans std :: vector而不是数组.

#include <iostream>
#include <vector>

using namespace std;

void quickSort(vector<int>&,int,int);

int partition(vector<int>&, int,int);

int main()
{
    vector<int> A = {6,10,13,5,8,3,2,25,4,11};
    int p=0;
    int q=10;

    cout<<"======Original======="<<endl;
    for(auto e: A)
        cout<< e <<" ";
    cout<< endl;    

    quickSort(A,p,q);

    cout<<"======Sorted======="<<endl;
    for(auto e: A)
        cout<< e <<" ";
    cout<< endl;   
}


void quickSort(vector<int>& A, int p,int q)
{
    int r;
    if(p<q)
    {
        r=partition(A, p,q);
        quickSort(A,p,r);  
        quickSort(A,r+1,q);
    }
}


int partition(vector<int>& A, int p,int q)
{
    int x= A[p];
    int i=p;
    int j;

    for(j=p+1; j<q; j++)
    {
        if(A[j]<=x)
        {
            i=i+1;
            swap(A[i],A[j]);
        }

    }

    swap(A[i],A[p]);
    return i;
}

实例:ideone