算法如下：
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] + " ");
}
}
}

现在问题来了，我这个程序可以完成对“每个元素都不一样”的数组的排序，但是遇到元素一样的情况就会失败。
比如{1,9,2,8,3,7,4,6}就可以排{1,9,9,2,8,3,7,4,6}就会排失败，会把其中一个9变成0。
跪求解决方法啊。
我之前尝试把findMiddle加上如下功能：
在small和big之间填入与pivot一样值的数，并且用一个整数equal来记录这些数的数量。
findMiddle返回一个长度为2的数组，第一位为small的最后值(即最多有多少个比pivot小的数)，第二位为small+equal（即big的数的前一位）。
然后把qSort的参数改成相应的这个数组的两位进行递归，还是失败了。程序如下。
public static void qSort(int[]a, int low, int high){
int[]x=new int[2];
if(high>low){
x=findMiddle(a,low,high);
qSort(a,low,x[0]);
qSort(a,x[0]+x[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 equal=0;
int p=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];
}
}
equal=c.length-small-big;
for(int j=small;j<big;j++){
c[j]=p;
}
for(int i=0;i<c.length;i++){
a[i+low]=c[i];
}
int[]x={low+small,equal};
return x;
}
求解啊，明天要交作业。

挽尊

挽尊

挽尊

挽尊

挽尊

深圳中学的 犀利啊
快排是交换类排序，操作只有交换 ，怎么会变值呢？（9变成0）
你看看标准快排的写法吧，
int small = 0;
int big = 0;
int equal=0;
没细看代码不知道弄这些变量是闹哪样，正常不需要这些额外的东西
只需要一个变量(如arr[0])存放key（中枢）,一个low指针和一个high指针

楼主是在实现快排还是在改进快排？

你的第一个写法 int equal=0;后面加入 int theSameCount = 0;
else if(a[i]>p) {
big++;
c[c.length-big]=a[i];
}
加入
else{
theSameCount ++;
}
c[small]=pivot;改成
for(int i=0;i<theSameCount;i++){
c[small+i]=pivot;
}

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 theSameCount = 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];
}else{
theSameCount ++;
}
}
for(int i=0;i<theSameCount;i++){
c[small+i]=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] + " ");
}
}
}

敢不敢发图

int result[];
result = findMiddle(...);
mid = result [0];
span = result [1];
qSort(a,low,mid);
qSort(a,mid+span ,high);
... findMiddle(...){
...
return [low+small,theSameCount];
}