我正在尝试创建递归合并排序,但不确定为什么它不起作用。我已经阅读了其他线程并尝试调试,但是最终结果未排序,并且一个元素将变为其他内容。这是代码:
public static <E extends Comparable<E>> void mergeSort(E[] array){
mergeSortRec(array, 0, array.length-1);
}
private static <E extends Comparable<E>> void mergeSortRec(E[] array, int firstIndex, int lastIndex){
//base case: if length of array is 1
if (firstIndex == lastIndex)
//return on void method: terminates method
return;
//split the array
int mid = (firstIndex + lastIndex)/2;
//recursive case
mergeSortRec(array, firstIndex, mid);
mergeSortRec(array, mid+1, lastIndex);
merge(array, firstIndex, mid, mid+1, lastIndex );
}
private static <E extends Comparable<E>> E[] merge(E[] array, int leftFirst, int leftLast, int rightFirst, int rightLast){
//create temporary array whose size equals (rightLast - leftFirst + 1)
E tmp[] = (E[]) Array.newInstance(array.getClass().getComponentType(), rightLast - leftFirst + 1);
int indexLeft = leftFirst;
int indexRight = rightFirst;
int index = 0;
while(indexLeft < leftLast && indexRight < rightLast){
//left half element is smaller
if (array[indexLeft].compareTo(array[indexRight]) < 0){
tmp[index] = array[indexLeft];
indexLeft++;
}
//right half element is smaller
else{
tmp[index] = array[indexRight];
indexRight++;
}
index++;
}
//add remaining elements to list
while(indexLeft < leftLast){
tmp[index] = array[indexLeft];
indexLeft++;
index++;
}
while(indexRight < rightLast){
tmp[index] = array[indexRight];
indexRight++;
index++;
}
//copy tmp to list
System.arraycopy(tmp, 0, array, 0, tmp.length);
return array;
}
由于开始索引和结束索引都包含在内,这意味着合并功能中的while条件应使用<=。另外,在最后进行arraycopy时,请确保array的起始索引为leftFirst,而不是0。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句