一个快速排序运行时出现问题？
这是代码：
-------------------------
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.java
D:\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)
-----------------------------------
[解决办法]
你在程序中调用时数组时越界了。
j=x+1;
r[i]=r[j];
这地方就有错
[解决办法]
标准快速排序，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()
}
[解决办法]
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;
}
[解决办法]
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;
}
}