快速排序
快速排序的描述
快排和归并排序一样，都是运用分治的思想
实现方法
存在数组A[p..r]，将他分成A[p,q-1],A[q],A[q+1,r]三部分，且存在A[p,q-1]<=A[q]<=A[q+1,r]关系，然后在递归调用快速排序，对A[p,q-1]，A[q+1,r]进行排序
图过程
(i)中，A[q]为4，4前面部分是A[p,q-1]，4后面部分是A[q+1,r]，然后在对A[p,q-1]，A[q+1,r]进行如图所示的方法
快排中间步骤图分析
将A[r]看作一个中间值，如果A[j] <= A[r],则A[j]与A[i+1]的值互换，让A[j]的值进入A[p,i]中，
如A[j] > A[r]的值，j++，将A[j]的值进入A[i,j]中
最后就会形成(h)的步骤，这时候将A[r]与A[i+1]互换，使得A[p,i]<=A[i+1]<=A[i+2,r]
代码
int partition(int *A, int p, int r) //小于大于A[r]的区分出来
{
int i = p-1;
for(int j = p; j < r; j++) {
if(A[j] <= A[r]) { //小于A[r]的放到左边分区
i++;
swap(A[i],A[j]);
}
}
swap(A[i+1],A[r]); //A[r]放到中间
return i+1; //返回坐标
}
void quicksort(int *a, int p, int r)
{
if(p < r) {
q = partition(A, p, r); //分区划分点
quicksort(A, p, q-1); //A[q]左分区快排
quicksort(A, q+1, r); //A[q]右分区快排
}
}