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

“`” 参考回答：

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

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

代码：

<pre><code>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);
}

</code></pre>

<pre><code> "“`