一个快速排序运行时出现问题？

Question

这是代码：
-------------------------------------------------------------
public void quicksort(int[] r,int low,int high){
int pivo;
if(low<high){
pivo=partition(r,low,high);
quicksort(r,low,pivo-1);
quicksort(r,pivo+1,high);
}
}
public int partition(int[] r,int z,int x){
int i,j,temp,pivot;
i=z;
j=x+1;
pivot=r[i];
while(i<j){
while(pivot<=r[j])j--;
if(i<j){
r[i]=r[j];
i++;
}
while(pivot>=r[i])i++;
if(i<j){
r[j]=r[i];
j--;
}
}//while end
r[i]=pivot;
return i;
}//快速排序结束public static void main(String arge[]){
int [] num=new int[10];
num[0]=111;
num[1]=68;
num[2]=18;
num[3]=38;
num[4]=88;
num[5]=98;
num[6]=78;
num[7]=58;
num[8]=48;
num[9]=28;
Sort ss=new Sort();
ss.quicksort(num,0,9);
for(int a=1;a<num.length;a++)
System.out.println(num[a]);
}
--------------------------------------------------------------编译可以通过，运行出现如下错误：--------------------------------------------------------------
D:\java>javac Sort.javaD:\java>java Sort
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10
        at Sort.partition(Sort.java:68)
        at Sort.quicksort(Sort.java:57)
        at Sort.main(Sort.java:98)
-----------------------------------------------------------------------

Answer 1

你在程序中调用时数组时越界了。j=x+1;
r[i]=r[j];这地方就有错

Answer 2

标准快速排序，lz参考一下；package org.luyang.collections;class ArrayIns {
    private long[] theArray; // ref to array theArray    private int nElems; // number of data items
    // --------------------------------------------------------------    public ArrayIns(int max) // constructor
    {
        theArray = new long[max]; // create the array
        nElems = 0; // no items yet
    }    // --------------------------------------------------------------
    public void insert(long value) // put element into array
    {
        theArray[nElems] = value; // insert it
        nElems++; // increment size
    }    // --------------------------------------------------------------
    public void display() // displays array contents
    {
        System.out.print("A=");
        for (int j = 0; j < nElems; j++)
            // for each element,
            System.out.print(theArray[j] + " "); // display it
        System.out.println("");
    }    // --------------------------------------------------------------
    public void quickSort() {
        recQuickSort(0, nElems - 1);
    }    // --------------------------------------------------------------
    public void recQuickSort(int left, int right) {
        if (right - left <= 0) // if size <= 1,
            return; // already sorted
        else // size is 2 or larger
        {
            long pivot = theArray[right]; // rightmost item
            // partition range
            int partition = partitionIt(left, right, pivot);
            recQuickSort(left, partition - 1); // sort left side
            recQuickSort(partition + 1, right); // sort right side
        }
    } // end recQuickSort()
    // --------------------------------------------------------------    public int partitionIt(int left, int right, long pivot) {
        int leftPtr = left - 1; // left (after ++)
        int rightPtr = right; // right-1 (after --)
        while (true) { // find bigger item
            while (theArray[++leftPtr] < pivot)
                ; // (nop)
            // find smaller item
            while (rightPtr > 0 && theArray[--rightPtr] > pivot)
                ; // (nop)            if (leftPtr >= rightPtr) // if pointers cross,
                break; // partition done
            else
                // not crossed, so
                swap(leftPtr, rightPtr); // swap elements
        } // end while(true)
        swap(leftPtr, right); // restore pivot
        return leftPtr; // return pivot location
    } // end partitionIt()
    // --------------------------------------------------------------    public void swap(int dex1, int dex2) // swap two elements
    {
        long temp = theArray[dex1]; // A into temp
        theArray[dex1] = theArray[dex2]; // B into A
        theArray[dex2] = temp; // temp into B
    } // end swap(
    // --------------------------------------------------------------
} // end class ArrayIns
// //////////////////////////////////////////////////////////////class QuickSort1App {
    public static void main(String[] args) {
        int maxSize = 16; // array size
        ArrayIns arr;
        arr = new ArrayIns(maxSize); // create array        for (int j = 0; j < maxSize; j++) // fill array with
        { // random numbers
            long n = (int) (java.lang.Math.random() * 99);
            arr.insert(n);
        }
        arr.display(); // display items
        arr.quickSort(); // quicksort them
        arr.display(); // display them again
    } // end main()
}

Answer 3

按楼上把那j=x+1；改成了j=x;但还是不行啊，报下面的错，
D:\java>java Sort
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10
        at Sort.partition(Sort.java:73)
        at Sort.quicksort(Sort.java:57)
        at Sort.main(Sort.java:98)

Answer 4

public int partition(int[] r,int z,int x){
int i,j,temp,pivot;
i=z;
j=x;
pivot=r[i];
while(i<j){
while( i < j && pivot<=r[j]) // 这里条件
                    j--;
//if(i<j){
r[i]=r[j];
// i++;
// }
while(i < j && pivot>=r[i]) // 这里条件
                    i++;
// if(i<j){
r[j]=r[i];
// j--;
// }
}//while end
r[i]=pivot;
return i;
}

Answer 5

public class Test
{
   public static void main(String arge[]){
int [] num=new int[10];
num[0]=111;
num[1]=68;
num[2]=18;
num[3]=38;
num[4]=88;
num[5]=98;
num[6]=78;
num[7]=58;
num[8]=48;
num[9]=28;
//Sort ss=new Sort();
quicksort(num,0,9);
for(int a=0;a<num.length;a++)
System.out.println(num[a]);
}
public static void quicksort(int[] r,int low,int high){
int pivo;
if(low<high){
pivo=partition(r,low,high);
quicksort(r,low,pivo-1);
quicksort(r,pivo+1,high);
}
}
public static int partition(int[] r,int z,int x){
int i,j,temp,pivot;
i=z;
j=x;
pivot=r[i];
while(i<j){
while(i < j && pivot<=r[j]) j--;
if(i<j){
r[i]=r[j];
i++;
}
while(i < j && pivot>=r[i]) i++;
if(i<j){
r[j]=r[i];
j--;
}
}//while end
r[i]=pivot;
return i;
}}

Answer 6

谢谢大家的热心帮助，laziogo() 、wuheng66888(吴恒)都对了，原来还要加一个条件，避免数组越界。