歸并排序的優點不說了。
做歸并排序之前，我先試著將兩個有序數組進行排序，合并成一個有序數組。
思路：定義好兩個有序數組，理解的時候我先思考了數組只有一個數組的排序，然后是兩個元素的數組的排序，思路就有了，先比較兩個數組的首元素，誰更小就放入結果數組里面，然后指針下移，繼續比較，直到有一個數組為空，停止比較，因為是有序數組，那么不為空的數組后面的元素都比之前存入結果數組的要大，且是有序的，因此，只需將后面的數組存入結果數組即可。
接下來是代碼實現：
/* * 分治算法利用 * 兩個有序數組的合并 * 將有序數組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為數組頭尾指針。
新聞熱點
疑難解答
