算法如下：
findMiddle的作用是，把数组a的某一段（从low到high）进行操作，操作的内容是，选定这一段的第一个数（a[low]）为pivot，把所有比pivot小的数放pivot左边，比pivot大的数放pivot右边（不用考虑左右两边的排序）。最后return pivot的位置。
其中small记录比pivot小的数的个数，big记录比pivot大的数的个数。
然后新建一个长度为high-low的数组c，把比pivot小的数从左到右填入c，把比pivot大的数从右到左填入c，最后在中间位置填pivot，return中间位置。
然后qSort方法是递归。
public class MathFunction{
public static void qSort(int[]a, int low, int high){
int mid;
if(high>low){
mid=findMiddle(a,low,high);
qSort(a,low,mid);
qSort(a,mid+1,high);
}
}
public static int findMiddle(int[] a, int low, int high) {
int c[] = new int[high-low];
int small = 0;
int big = 0;
int pivot=a[low];
for (int i = low; i < high; i++) {
if (a[i] < p) {
c[small]=a[i];
small++;
} else if(a[i]>p) {
big++;
c[c.length-big]=a[i];
}
}
c[small]=pivot;
for(int i=0;i<c.length;i++){
a[i+low]=c[i];
}
return low+small;
}
public static void main(String[] args){
int[]a={1,9,2,8,3,7,4,6,5};
MathFunction.qSort(a,0,a.length);
for (int i = 0; i <a.length; i++) {
System.out.print(a[i] + " ");
}
}
}

挽尊

挽尊

挽尊

挽尊

挽尊