我正在尝试在 Java 中实现 Coreman 的 MergeSort 算法。但它总是给我错误的输出。
排序前：[86, 8, 60, 9, 49, 73, 37, 59, 98, 69]
排序后：[8, 8, 9, 37, 37, 49, 49, 59, 69, 69]
以下是我的代码：
public class MergeSort {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
MergeSort mergeSort = new MergeSort();
int [] data = mergeSort.createRandomNumberArray();
mergeSort.print("Before sorting", data);
long startTime = System.currentTimeMillis();
mergeSort.sort(data);
long endTime = System.currentTimeMillis();
mergeSort.print("After Sorting", data);
mergeSort.time(startTime, endTime);
}
public void sort(int[] data) {
if(data == null)
throw new NullPointerException();
if(data.length == 0 || data.length == 1) {
System.out.println("Size is " + data.length);
return;
}
int length = data.length;
mergeSort(data, 0, length - 1);
}
/**
* @param data
* @param first
* @param last
*/
private void mergeSort(int[ ] data, int first, int last) {
if(first < last) {
int middle = (first + last) / 2;
mergeSort(data, first, middle);
mergeSort(data, middle + 1, last);
merge(data, first, middle, last);
}
}
private void merge(int[ ] data, int first, int middle, int end) {
int lSize = middle - first + 1;
int rSize = end - middle;
int [] left = new int[lSize + 1];
left[lSize] = Integer.MAX_VALUE;
int [] right = new int[rSize + 1];
right[rSize] = Integer.MAX_VALUE;
for(int i = 0; i < lSize; i++) {
left[i] = data[first + i];
}
for(int j = 0; j < rSize; j++) {
right[j] = data[middle + j + 1];
}
print("Left: ", left);
print("Right: ", right);
int lIndex = 0;
int rIndex = 0;
for(int k = first; k < end; k++) {
if(left[lIndex] <= right[rIndex]) {
data[k] = left[lIndex];
lIndex++;
} else {
data[k] = right[rIndex];
rIndex++;
}
}
}
public void print(String message, int [] array) {
System.out.println(message + " : " + Arrays.toString(array));
}
public int [] createRandomNumberArray() {
int [] data = new int[] {86,8,60,9,49,73,37,59,98,69} ;
/*int [] data = new int[SIZE];
for(int i = 0; i < SIZE; i++) {
data[i] = RANDOM.nextInt(RANGE);
}*/
return data;
}
public long time(long start, long end) {
long time = end - start;
System.out.println("Time taken in sorting ==> " + time);
return time;
}
}
我尝试打印值并调试代码，但无法找出这里出了什么问题。请在这里提出什么问题。