歸併排序演算法

歸併排序就是將未排序的數組進行對半劃分成兩個數組，劃分後的數組只有原來數組的一半數量的元素。然後在對劃分的兩個數組再繼續劃分，迴圈此操作，直到劃分的數組中只有一個元素時停止劃分，然後對於劃分完成的數組進行歸併排序操作。將兩個已經劃分完成的數組合併成一個有序的數組，直到最後合併成一個包含所有元素的數組，合併排序操作完成。下麵以圖形來演示下歸併排序的過程。

假設有一個未排序數組：｛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);
        }

歸併排序的時間複雜度為：O（nlogn），空間複雜度為：O（n）。