??今天在寫排序算法的時候，為了方便以后復(fù)習(xí)熏纯，把每一個排序算法都寫在方法里同诫。之前的交換排序、插入排序和選擇排序都沒有問題樟澜，雖然看到方法里接收值有一點(diǎn)疑惑误窖，但還是沒有仔細(xì)思考過。直到后面寫到了歸并排序秩贰，遇到坑了贩猎。
??直接上問題代碼：
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 ，現(xiàn)在看來確實很傻- -萍膛。
先簡單的解釋一下最后一個if-else的作用。
當(dāng)n即排序子序列長度嚷堡，小于數(shù)組X的長度時蝗罗，證明數(shù)組X還可以再一次合并到數(shù)組Y中，于是再做一次合并蝌戒。
當(dāng)n >= 數(shù)組X的長度時串塑，即表示已合并完。但是如代碼中所寫的北苟，我的合并是按 把X合并到Y(jié)中---->然后再把Y合并到X中---->把X合并到Y(jié)中·····這樣的順序進(jìn)行的桩匪。所以會有一種情況導(dǎo)致最后一次合并是把X合并到Y(jié)中，這樣數(shù)組X的值不會改變友鼻。于是我就順手加了一句else {x = y}傻昙。把數(shù)組Y的引用給數(shù)組X。
然而運(yùn)行的結(jié)果不對彩扔。
仔細(xì)看妆档，可以發(fā)現(xiàn)這個結(jié)果是上一趟的歸并排序結(jié)果，那么為什么我把排序好的Y給X后虫碉，并沒有生效呢贾惦。
于是我打了兩個斷點(diǎn)找一找問題的根源。
在運(yùn)行x = y 之前：
在這里可以發(fā)現(xiàn)對象X 指向的地址和 對象a指向的地址是同一個{int[8]@503}
在運(yùn)行x = y 之后：
這樣可以看到，當(dāng)運(yùn)行X = Y之后须板，只是把X指向了Y碰镜，而數(shù)組a并沒有任何變化。
由此得出結(jié)論：Java 只有值傳遞參數(shù)习瑰。當(dāng)一個對象實例作為一個參數(shù)被傳遞到方法中時绪颖，參數(shù)的值就是該對象的引用一個副本。指向同一個對象,對象的內(nèi)容可以在被調(diào)用的方法中改變杰刽，但對象的引用(不是引用的副本)是永遠(yuǎn)不會改變的菠发。
??如果參數(shù)類型是原始類型，那么傳過來的就是這個參數(shù)的一個副本贺嫂，也就是這個原始參數(shù)的值滓鸠，這個跟之前所談的傳值是一樣的。如果在函數(shù)中改變了副本的值不會改變原始的值第喳。
??如果參數(shù)類型是引用類型糜俗，那么傳過來的就是這個引用參數(shù)的副本，這個副本存放的是參數(shù)的地址曲饱。如果在函數(shù)中沒有改變這個副本的地址悠抹，而是改變了地址中的值，那么在函數(shù)內(nèi)的改變會影響到傳入的參數(shù)扩淀。如果在函數(shù)中改變了副本的地址楔敌，如new一個，那么副本就指向了一個新的地址驻谆，此時傳入的參數(shù)還是指向原來的地址卵凑，所以不會改變參數(shù)的值。
于是修改代碼：
for (int i = 0;i < X.length;i++) {
X[i] = Y[i];
}
這樣就完成了該歸并排序胜臊。
