歸並排序的優點不說了。
做歸並排序之前，我先試著將兩個有序數組進行排序，合並成一個有序數組。
思路：定義好兩個有序數組，理解的時候我先思考了數組只有一個數組的排序，然後是兩個元素的數組的排序，思路就有了，先比較兩個數組的首元素，誰更小就放入結果數組裡面，然後指針下移，繼續比較，直到有一個數組為空，停止比較，因為是有序數組，那麼不為空的數組後面的元素都比之前存入結果數組的要大，且是有序的，因此，只需將後面的數組存入結果數組即可。
接下來是代碼實現：
/*
* 分治算法利用
* 兩個有序數組的合並
* 將有序數組i,數組j,合並成c
*/
public Integer[] sort(Integer[] i, Integer[] j, Integer[] c){
c = new Integer[i.length+j.length];
int i1 = 0; //i的數組指針
int j1 = 0; //j的數組指針
int c1 = 0; //c的數組指針
while(i1 < i.length&&j1 < j.length){
if(i[i1] > j[j1]){
c[c1++] = j[j1];
j[j1++] = null;
}else{
c[c1++] = i[i1];
i[i1++] = null;
}
}
/*
* i之後還有元素
*/
while(i1<i.length){
c[c1++] = i[i1];
i[i1++] = null;
}
/*
* j之後還有元素
*/
while(j1 < j.length){
c[c1++] = j[j1];
j[j1++] = null;
}
return c;
}
以上實現了將兩個有序數組的合並，而歸並排序，那麼將一條無序數組分組成任意多個有序數組即可，並不需要確認是否是有序數組，一個數組裡一個元素肯定是有序的，那麼我要做的只是，遞歸實現數組分解，然後將有兩個序數組合並。
將一個數組分解，可以用分治的方法，定義頭，尾，和中間指針，然後下次的遞歸，只需變換中間指針即可。
而排序最開始只需要比較頭部的一個元素和尾部的一個元素；
依次向上遞歸。
算了，貼代碼吧。
public int[] mergeSort(int[] num,int first,int last){
int mid = (first+last)/2;
if(first < last){
mergeSort(num,first,mid);
mergeSort(num,mid+1,last);
merge(num,first,mid,last);
}
return num;
}
public void merge(int[] num,int first,int mid,int last){
int _left = first; //左指針
int _right = mid+1; //右指針
int[] temp = new int[last - first + 1];
int temp_p = 0;
while(_left<=mid&&_right<=last){
if(num[_left]<num[_right]){
temp[temp_p++] = num[_left++];
}else{
temp[temp_p++] = num[_right++];
}
}
while(_left<=mid){
temp[temp_p++] = num[_left++];
}
while(_right<=last){
temp[temp_p++] = num[_right++];
}
_left = 0;
//因為沒有返回數組，所以排序好的數組應該放在num數組裡面，直接覆蓋即可，注意下標。
for(int i : temp){
num[(_left++)+first] = i;
}
}
first，last為數組頭尾指針。
