今天在写排序算法的时候，为了方便以后复习，把每一个排序算法都写在方法里。之前的交换排序、插入排序和选择排序都没有问题，虽然看到方法里接收值有一点疑惑，但还是没有仔细思考过。直到后面写到了归并排序，遇到坑了。
直接上问题代码：
public class MergeSort {
public static void main(String[] args) {
int a[] = {3,1,5,7,2,4,9,6};
new MergeSort().mergeSort(a);
for (int i = 0;i < a.length;i++) {
System.out.print(a[i]+" ");
}
}
public void merge(int [] X, int [] Y, int begin1, int begin2,int n) {
int i = begin1;
int j = begin2;
int k = begin1;
while (i < begin1 + n && j < begin2 + n && j < X.length) {
if (X[i] < X[j]) {
Y[k++] = X[i++];
}else {
Y[k++] = X[j++];
}
}
while (i < begin1 + n && i < X.length) {
Y[k++] = X[i++];
}
while (j < begin2 + n && j < X.length) {
Y[k++] = X[j++];
}
}
public void mergePass(int [] X, int [] Y, int n) {
for (int i = 0;i < X.length; i = i + 2 * n) {
merge(X, Y, i, i + n, n);
}
}
public void mergeSort(int [] X) {
int [] Y = new int[X.length];
int n = 1;
while (n < X.length) {
mergePass(X, Y, n);
n = n * 2;
if (n < X.length) {
mergePass(Y, X, n);
n *= 2;
}else {
/* for (int i = 0;i < X.length;i++) {
X[i] = Y[i];
}*/
X = Y;
}
}
}
}
最后一步X = Y ，现在看来确实很傻- -。
先简单的解释一下最后一个if-else的作用。
当n即排序子序列长度，小于数组X的长度时，证明数组X还可以再一次合并到数组Y中，于是再做一次合并。
当n >= 数组X的长度时，即表示已合并完。但是如代码中所写的，我的合并是按 把X合并到Y中---->然后再把Y合并到X中---->把X合并到Y中·····这样的顺序进行的。所以会有一种情况导致最后一次合并是把X合并到Y中，这样数组X的值不会改变。于是我就顺手加了一句else {x = y}。把数组Y的引用给数组X。
然而运行的结果不对。
仔细看，可以发现这个结果是上一趟的归并排序结果，那么为什么我把排序好的Y给X后，并没有生效呢。
于是我打了两个断点找一找问题的根源。
在运行x = y 之前：
在这里可以发现对象X 指向的地址和 对象a指向的地址是同一个{int[8]@503}
在运行x = y 之后：
这样可以看到，当运行X = Y之后，只是把X指向了Y，而数组a并没有任何变化。
由此得出结论：Java 只有值传递参数。当一个对象实例作为一个参数被传递到方法中时，参数的值就是该对象的引用一个副本。指向同一个对象,对象的内容可以在被调用的方法中改变，但对象的引用(不是引用的副本)是永远不会改变的。
如果参数类型是原始类型，那么传过来的就是这个参数的一个副本，也就是这个原始参数的值，这个跟之前所谈的传值是一样的。如果在函数中改变了副本的值不会改变原始的值。
如果参数类型是引用类型，那么传过来的就是这个引用参数的副本，这个副本存放的是参数的地址。如果在函数中没有改变这个副本的地址，而是改变了地址中的值，那么在函数内的改变会影响到传入的参数。如果在函数中改变了副本的地址，如new一个，那么副本就指向了一个新的地址，此时传入的参数还是指向原来的地址，所以不会改变参数的值。
于是修改代码：
for (int i = 0;i < X.length;i++) {
X[i] = Y[i];
}
这样就完成了该归并排序。
