参考答案

参考回答：

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

代码：

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