快排

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

核心是分治

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

然后完成分割操作

最后确定递归条件！

[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 {
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 {
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< }
cout <

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< }
cout <