快排

最近在看算法導論，就實現了一些簡單的算法！

核心是分治

首先先完成交換兩個值的函數，

然後完成分割操作

最後確定遞歸條件！

[cpp] int exchange(int A[],int i,int j) 
{ 
    int temp    = A[i]; 
    A[i]        = 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[i];
 A[i]  = 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[i]<<"\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[i]<<"\t";
 }
 cout <<endl;