请你说一下快排如何实现？

Answer 1

参考回答：

首先选择一个轴值，小于轴值的元素被放在数组中轴值左侧，大于轴值的元素被放在数组中轴值右侧，这称为数组的一个分割(partition)。快速排序再对轴值左右子数组分别进行类似的操作

选择轴值有多种方法。最简单的方法是使用首或尾元素。但是，如果输入的数组是正序或者逆序时，会将所有元素分到轴值的一边。较好的方法是随机选取轴值

代码：

template <class Elem>
int partition(Elem A[],int i,int j)
{
//这里选择尾元素作为轴值,轴值的选择可以设计为一个函数
//如果选择的轴值不是尾元素，还需将轴值与尾元素交换

    int pivot = A[j];
    int l = i - 1;
    for(int r = i;r < j;r++)
    if(A[r] <= pivot)
    swap(A,++l,r);
    swap(A,++l,j);//将轴值从末尾与++l位置的元素交换
	return l;
}
template <class Elem>
void qsort(Elem A[],int i,int j)
{
if(j <= i)  return;
int p = partition<Elem>(A,i,j);
qsort<Elem>(A,i,p - 1);
qsort<Elem>(A,p + 1,j);
}