参考回答：
首先选择一个轴值，小于轴值的元素被放在数组中轴值左侧，大于轴值的元素被放在数组中轴值右侧，这称为数组的一个分割(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);}
