參考鏈接： Java中將數組合并為的新數組

歸并排序?

大家好，這是我第一次在CSDN上寫東西，因為我一直覺得有需要就去找別人的blog看看就好，但我發現自己寫出來的東西確實能加深記憶。我半路出家，屬實是個菜鳥，文章也許寫的會有很多問題，還望大家多多包涵，歡迎指正。 最近在學數據結構，數據結構作為程序員該有的基本內功，無疑是我們要多加練習的。然而最為菜鳥的我，在學習的過程中也發現很多坑在大佬眼里不就是一句話的事 ，我寫的這些既是為了幫助有需要的人，也是對自己的鍛煉以及記錄。廢話到此結束，再多說要被錘了。?

代碼打頭?

~~廢話不多說先上代碼，如果代碼都跑不出，大家就可以散了。~~?

?

?

import java.util.Arrays;

?

public class mergeSortDemo {

? ? public static void main(String[] args) {

? ? ? ? int arr[] = new int[10];

? ? ? ? for (int i = 0;i<arr.length;i++){

? ? ? ? ? ? arr[i] = (int) (Math.random()*100);

? ? ? ? }

? ? ? ? for (int i=0;i<arr.length;i++){

? ? ? ? ? ? System.out.print(arr[i]+" ");

? ? ? ? }

? ? ? ? System.out.println("~~~~~~~~~~");

? ? ? ? mergeSort(arr,0,9);

? ? }

?

? ? public static void merge(int arr[],int low,int mid,int high){

? ? ? ? int i = low;

? ? ? ? int j = mid+1;

? ? ? ? int t = 0;

? ? ? ? int temp[] = new int[high-low+1];

? ? ? ? while (i<=mid && j<=high){

? ? ? ? ? ? if (arr[i]<arr[j]){

? ? ? ? ? ? ? ? temp[t++] = arr[i++];

? ? ? ? ? ? }

? ? ? ? ? ? else {

? ? ? ? ? ? ? ? temp[t++] = arr[j++];

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? //

? ? ? ? while (i<=mid){

? ? ? ? ? ? temp[t++] = arr[i++];

? ? ? ? }

? ? ? ? while (j<=high){

? ? ? ? ? ? temp[t++] = arr[j++];

? ? ? ? }

? ? ? ? //

? ? ? ? for (int tempLeft=0;tempLeft<temp.length;tempLeft++){

? ? ? ? ? ? arr[low+tempLeft] = temp[tempLeft];

? ? ? ? }

? ? }

? ? public static void mergeSort(int arr[],int low,int high){

? ? ? ? int mid = (low+high)/2;

? ? ? ? if (low<high) {

? ? ? ? ? ? mergeSort(arr, low, mid);

? ? ? ? ? ? mergeSort(arr, mid+1, high);

? ? ? ? ? ? //

? ? ? ? ? ? merge(arr,low,mid,high);

? ? ? ? ? ? System.out.println( Arrays.toString(arr));

? ? ? ? }

? ? }

}

?

?

?

是不是被這精妙的邏輯給迷住了。 何謂歸并排序，歸并排序就是divide-and-merge。?

如圖，算法的基本做法是：先分割數字，再按照每組的的大小排序，兩個小組變為中組，兩個中組合為大組。??

整體思路?

歸并排序首先需要將數組拆分，然后治之。具體為，將一串數組分為兩半，再各自對兩半繼續拆分，直至每組的的元素個數為一。此時開始治：如圖中將數據分到最后一步，則上層長度為2，用當前的兩個數組，按照算法來排序整合merge（）{① 比較兩個數組中的每一個數，將當前索引指向的較小的數裝入臨時數組temp中；② 當一組數據全部裝入temp中時，一定會出現一種情況，另一組一定還有數據沒存進去，所以將剩下的數存入temp；③ 這是比較難想到的一點：存入temp后，還需要返回到原先數組arr【】中去。但注意，雖然每次都是返回去的下標都是從0—>length-1，但不是一次性的。因為整個排序不是一次排好，每次小組內排完就需要存回arr，由此可知，不可能只用回傳一次，但每次當然要把所有數據都穿回去，但是是分批進行，這也是這個算法的難點與精髓所在。為了方便理解，我用迭代的方式向大家展示：最后一次（也是最接近排序完成的一次）是兩個數組合并為一個，這一個temp傳回給arr【】，是從temp【0】->temp【length-1】。倒數第二次：temp【0】->temp【mid】，temp【mid+1】->temp【length-1】…第一次：兩兩回傳，（可能是）temp【0】->temp【1】，temp2->temp3依次類推。這就肯定需要循環來定位索引。?

到此可以將上述方法抽象為 mergeSort（）和merge（）。mergeSort（）多次遞歸調用自己而每次調用意味著分，分則要治，治則是在調用后用merge（）。?

從圖上可以清晰的看出，整個操作是棧式操作，先分的最后再合，當然遞歸本身就是棧式操作，我之所以這樣說是為了讓大家再順著思路分析下來能知道如何去編寫這樣的程序。有了這些，我們開始逐句翻譯就好了。 我們知道需要一個分的總函數以及每次幫忙合的子函數，總函數遞歸調用自己和子函數就完成了。故此，我們開始子函數的編寫，也是按照之前的思路。?

實現?

merge（）{①比較兩個數組中的每一個數，將當前索引指向的較小的數裝入臨時數組temp中；?

merge(int arr[],int low,int mid,int high){

? ? ? ? ? ? int i = low;

? ? ? ? ? ? int j = mid+1;

? ? ? ? ? ? int t = 0;

? ? ? ? ? ? int temp[] = new int[high-low+1];

? ? ? ? while (i<=mid && j<=high){

? ? ? ? ? ? if (arr[i]<arr[j]){

? ? ? ? ? ? ? ? temp[t++] = arr[i++];

? ? ? ? ? ? }

? ? ? ? ? ? else {

? ? ? ? ? ? ? ? temp[t++] = arr[j++];

? ? ? ? ? ? }

?

?

②當一組數據全部裝入temp中時，一定會出現一種情況，另一組一定還有數據沒存進去，所以將剩下的數存入temp；?

?while (i<=mid){

? ? ? ? ? ? temp[t++] = arr[i++];

? ? ? ? }

? ? ? ? while (j<=high){

? ? ? ? ? ? temp[t++] = arr[j++];

? ? ? ? }

?

?

③ 這是比較難想到的一點：存入temp后，還需要返回到原先數組arr【】中去。但注意，雖然每次都是返回去的下標都是從0—>length-1，但不是一次性的。因為整個排序不是一次排好，每次小組內排完就需要存回arr，由此可知，不可能只用回傳一次，但每次當然要把所有數據都穿回去，但是是分批進行，這也是這個算法的難點與精髓所在。為了方便理解，我用迭代的方式向大家展示：最后一次（也是最接近排序完成的一次）是兩個數組合并為一個，這一個temp傳回給arr【】，是從temp【0】->temp【length-1】。倒數第二次：temp【0】->temp【mid】，temp【mid+1】->temp【length-1】…第一次：兩兩回傳，（可能是）temp【0】->temp【1】，temp2->temp3依次類推。這就肯定需要循環來定位索引。?

for (int tempLeft=0;tempLeft<temp.length;tempLeft++){

? ? ? ? ? ? arr[low+tempLeft] = temp[tempLeft];

? ? ? ? }

?

?

mergeSort（）多次遞歸調用自己而每次調用意味著分，分則要治，治則是在調用后用merge（）。 我們都知道要一分為二二分為四，到元素為一時結束，反過來怎么寫循環呢。當length=1 則（0+1）/2=0 此時low=high 反過來 low<high則可以不停分解?

mergeSort(int arr[],int low,int high){

? ? ? ? int mid = (low+high)/2;

? ? ? ? if (low<high) {

? ? ? ? ? ? mergeSort(arr, low, mid);

? ? ? ? ? ? mergeSort(arr, mid+1, high);

? ? ? ? ? ? //

? ? ? ? ? ? merge(arr,low,mid,high);

? ? ? ? ? ? System.out.println( Arrays.toString(arr));

? ? ? ? }

? ? }

?

?

分析?

首先要將整個數組遍歷一遍，歸并排序要進行log2n次，總共的時間復雜度為O（nlog2n）?

遞歸深度為log2n 額外的數組空間 n 總的空間復雜度為O（n+log2n）?

再merge（）中使用的是兩兩比較，不存在跳躍，所以歸并排序是穩定的。?

換而言之，歸并排序是一種空間換時間的算法。?

謝謝大家。?

圖侵刪