我一直在尝试让我的归并排序方法工作,但它给了我一些时髦的输出。
// mergesort method
// recursively sorts the array by breaking into small sub-arrays and then merging
public static int[] mergeSort(int[] nums){
int halfwayAndOne = (nums.length / 2);
int a = 0, b = 0;
if (nums.length <= 1)
return nums;
else{
int[] l = new int[nums.length / 2];
int[] r = new int[nums.length - l.length];
for (int i = 0; i < l.length; i++)
l[i] = nums[i];
for (int j = 0; j < nums.length - l.length; j++){
r[j] = nums[halfwayAndOne];
halfwayAndOne++;
}
for (int n = 0; n < nums.length; n++){
if (a < l.length && b < r.length) {
if (l[a] < r[b]) {
nums[n] = l[a];
a++;
} else {
nums[n] = r[b];
b++;
}
}
else if (a == l.length)
nums[n] = r[b];
else
nums[n] = l[a];
}
mergeSort(l);
mergeSort(r);
printArr(l);
printArr(r);
return nums;
}
}
// method to print out the array
public static void printArr(int[] arr){
System.out.println(Arrays.toString(arr));
}
输出:
[4, 0, 10, 15, 2, 1, 8, 9, 20, 3, 5]
[4]
[0]
[15]
[2]
[10]
[2, 15]
[0, 4]
[10, 15, 15]
[8]
[9]
[1]
[8, 9]
[3]
[5]
[20]
[3, 5]
[1, 8, 8]
[3, 5, 20]
[4, 0, 10, 10, 10]
[1, 8, 9, 20, 20, 20]
[1, 4, 0, 8, 9, 10, 15, 2, 20, 20, 20]
第一个数组是原始数组,输出应该从最小到最大排序
编辑:我的问题是哪里是我的程序不工作,认为这是不言自明的,对不起。
在您将l
和r
合并回nums
的地方,l
和r
已经排序了吗?