[C++技术]C++快排

最近在看算法导论，就实现了一些简单的算法！

核心是分治

首先先完成交换两个值的函数，

然后完成分割操作

最后确定递归条件！


[cpp] int exchange(int A[],int i,int j)
{
    int temp    = A;
    A        = A[j];
    A[j]    = temp;
    return 0;
}
int Partion(int A[],int p,int r)
{
    int x= A[r];
 
    int i = p-1;
 
    for (int j = p; j < r; j++)
    {
        if (A[j]<=x)
        {
            i = i+1;
            exchange(A,i,j);
        }
    }
    exchange(A,i+1,r);
    return i+1;
}
 
void QuickSort(int A[],int p,int r)
{
    if (p<r-1)
    {
        int q = Partion(A,p,r);
        QuickSort(A,p,q-1);
        QuickSort(A,q+1,r);
    }
}

int exchange(int A[],int i,int j)
{
 int temp = A;
 A  = A[j];
 A[j] = temp;
 return 0;
}
int Partion(int A[],int p,int r)
{
 int x= A[r];

 int i = p-1;

 for (int j = p; j < r; j++)
 {
  if (A[j]<=x)
  {
   i = i+1;
   exchange(A,i,j);
  }
 }
 exchange(A,i+1,r);
 return i+1;
}

void QuickSort(int A[],int p,int r)
{
 if (p<r-1)
 {
  int q = Partion(A,p,r);
  QuickSort(A,p,q-1);
  QuickSort(A,q+1,r);
 }
}

 

测试快排的代码：
[cpp] int A[10]={2,3,4,5,6,7,8,9,0,1};
 
QuickSort(A,0,9);
 
    for (int i = 0; i <10; i++)
    {
        cout<<A<<"\t";
    }
    cout <<endl;

int A[10]={2,3,4,5,6,7,8,9,0,1};

QuickSort(A,0,9);

 for (int i = 0; i <10; i++)
 {
  cout<<A<<"\t";
 }
 cout <<endl;