Question

请大神帮我看看这个归并排序错在哪里？？？

private void mergeSort(int[] a) {

int n = a.length;
int[] b = null, c = null;
while (n > 1) {
b = new int[n / 2];
c = new int[n - n / 2];

for (int i = 0, j = 0; i < n; i++) {
if (i < n / 2) {
b[i] = a[i];
} else {
c[j] = a[i];
j++;
}
}

mergeSort(b);
mergeSort(c);
merge(b, c, a);
}

}

private void merge(int[] b, int[] c, int[] a) {

int i = 0, j = 0, k = 0;
while (i < b.length && j < c.length) {
if (b[i] < c[j]) {
a[k] = b[i];
i++;
} else {
a[k] = c[j];
j++;
}
k++;
}

if (i == b.length) {
for (; j < c.length; j++, k++) {
a[k] = b[j];
}
} else {
for (; i < b.length; i++, k++) {
a[k] = b[i];
}
}
}

Answer 1

1、错误在于递归调用中使用的while错误使用和部分逻辑不严格。

2、方法mergeSort方法在自身方法体中被调用是典型的递归用法，递归调用包含类似while的功能。B部分的while因为没有终结限制（n没有递减）造成了程序的死循环。给方法应在A出添加数组返回值，去掉B处的while代之以if(a<2){return a}的终结条件，把merge方法的返回值作为该方法的返回值。

3、D处的a[k]=b[j]应该为a[k]=c[j]。merge方法应添加返回int[]数组类型，返回a[]

追问

真的很感谢，我纠结了很久居然然没有想到返回值，真不好意思，还犯了一些低级错误。。。while（n>1）循环应该没有问题吧，因为n是数组长度

追答

1、每一次递归调用都相当与单独执行一次mergeSort方法。根据你的程序假设一个分支n的值为8、4、2，则第一次调用mergeSort方法时n=8,因为在再次递归之前（调用mergeSort）n的值在循环中没有递减所以while循环就会死循环。
2、你可以使用eclipse调试模式看下。