歸并排序就是將未排序的數組進行對半劃分成兩個數組，劃分后的數組只有原來數組的一半數量的元素。然后在對劃分的兩個數組再繼續劃分，循環此操作，直到劃分的數組中只有一個元素時停止劃分，然后對于劃分完成的數組進行歸并排序操作。將兩個已經劃分完成的數組合并成一個有序的數組，直到最后合并成一個包含所有元素的數組，合并排序操作完成。下面以圖形來演示下歸并排序的過程。
假設有一個未排序數組：｛3，2，4，1｝，下面為數組的劃分過程，先將數組對半劃分為｛3，2｝和｛4，1｝兩個數組。然后在對這兩個數組進行劃分最后得到｛3｝，｛2｝，｛4｝，｛1｝四個數組，劃分完成。
接下來對數組進行歸并，先將｛3｝和｛2｝這兩個數組合并成一個有序的數組｛2，3｝，同理對4，1進行相同的操作，得到｛1，4｝，然后在將合并好的這兩個有序數組進行合并，最后合并成｛1，2，3，4｝，歸并完成。
歸并排序算法用java代碼實現如下：
public static void MergeSort(int[] array,int head,int tail){ // 判斷數組的頭部索引是否小于尾部索引 if(head < tail){ int middle = (head+tail)/2; MergeSort(array,head,middle); MergeSort(array,middle+1,tail); Merge(array,head,middle,tail); } } public static void Merge(int[] array, int head, int middle, int tail) { // TODO Auto-generated method stub int[] temp = new int[tail - head + 1]; int a = head; int b = middle + 1; int i = 0; // 對于兩個數組中的數進行比較，將較小的值存放在臨時數組中 while(a <= middle && b <=tail){ if(array[a] < array[b]){ temp[i++] = array[a++]; } else{ temp[i++] = array[b++]; } } // 將未參與比較的數組中的數添加到臨時數組中 while(a <= middle){ temp[i++] = array[a++]; } while(b <= tail){ temp[i++] = array[b++]; } // 將排好序的數組放回到array數組中 System.arraycopy(temp,0,array,head,tail - head + 1); }新聞熱點
疑難解答
