我正在开发一个修改版的快速排序,它使用了
((lowIndex + highIndex) / 2)
我的代码在下面。但是,无论何时运行它,都会出现以下错误:
start ARRAY
1
2
10
9
3
4
8
7
5
6
Exception in thread "main" java.lang.StackOverflowError
at newQuickSort.quicksort(newQuickSort.java:37)
at newQuickSort.quicksort(newQuickSort.java:39)
at newQuickSort.quicksort(newQuickSort.java:39)
是重复的。
从本质上说,我只是想把配分函数改为使用三分之一的中位数,而不是真正接触快速排序算法,只是配分函数。
我不太清楚为什么会发生这个错误,尽管我引用了以下内容:
任何建议都会有帮助,谢谢!
public class newQuickSort{
static int count;
static void move(int myArray[], int a, int b){
int temp;
temp = myArray[a];
myArray[a] = myArray[b];
myArray[b] = temp;
} //end move
//Create the partition function
static int partition(int myArray[], int p, int r){
int medIndex = (p+r) / 2;
int pivot;
if (myArray[p] > myArray[medIndex]){
move(myArray, p, medIndex);
}else if (myArray[p] > myArray[r]){
move(myArray, p, r);
}else if (myArray[medIndex] > myArray[r]){
move(myArray, medIndex, r);
}
//end if checks
//now set proper movements
move(myArray, medIndex, r-1);
//set pivot
pivot = myArray[r-1];
//return pivot for which to partition around
return pivot;
} //end partition
static void quicksort(int myArray[], int p, int r){
if (p < r){
checkCount += 1;
int partition = partition(myArray, p, r);
quicksort(myArray, p, partition-1);
quicksort(myArray, partition+1, r);
} //end if
} //end quicksort
public static void main (String[] args){
int testarray[] = {1,2,10,9,3,4,8,7,5,6};
// int testarray[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
System.out.println("start ARRAY");
for (int i = 0; i < testarray.length; i++){
System.out.println(testarray[i]);
} //end for
int p = 0;
int r = testarray.length-1;
newQuickSort mySort = new newQuickSort();
mySort.quicksort(testarray, p, r);
System.out.println("end ARRAY");
for (int j = 0; j < testarray.length; j++){
System.out.println(testarray[j]);
} //end for
}
}