0. 前言

本系列文章將介紹一些常用的排序算法。排序是一個非常常見的應用場景，也是開發崗位面試必問的一道面試題，有人說，如果一個企業招聘開發人員的題目中沒有排序算法題，那說明這個企業不是一個“正規”的企業，哈哈，雖然有點戲謔，但是也從側面證明了排序算法的重要性。

本文將介紹的是常見排序算法中的歸并排序。

8  歸并排序

8.1  基本思想

歸并排序是指通過對若干個有序結點序列的歸并來實現排序，所謂歸并是指將若干個已排好序的部分根據算法合并成一個新的有序整體。

比如兩個有序的子序列array[low,...,mid]和array[mid+1,...,high]，設置i,j兩個指針指向low和mid+1，合并時依次比較array[i]和array[j]的值，取較小值記錄復制到暫存序列temp[]中，在用p指向該暫存序列，每復制一次，讓較小值的下標i或者j自增一次，同時p也自增一次。重復這一過程直至兩個子序列中有一個已全部復制完畢，此時將另一非空的子序列中的剩余數據依次復制到array中即可。

8.2  代碼實現

/**@author Calvin*@blog http://blog.csdn.net/seu_calvin/article/details/60129650*@data 2017/03/3*/public class Order {	    public static void sort(int[] nums, int low, int high) {          int mid = (low + high) / 2;          if (low < high) {              // 左邊              sort(nums, low, mid);              // 右邊              sort(nums, mid + 1, high);              // 左右歸并              //最后一次執行該句時，是重排所有元素，遞歸調用時是排子序列            merge(nums, low, mid, high);          }      }        public static void merge(int[] nums, int low, int mid, int high) {          int[] temp = new int[high - low + 1];          int i = low;// 左指針          int j = mid + 1;// 右指針          int k = 0;            // 把較小的數先移到新數組中          while (i <= mid && j <= high) {              if (nums[i] < nums[j]) {                  temp[k++] = nums[i++];              } else {                  temp[k++] = nums[j++];              }          }            // 把左邊剩余的數移入數組          while (i <= mid) {              temp[k++] = nums[i++];          }            // 把右邊邊剩余的數移入數組          while (j <= high) {              temp[k++] = nums[j++];          }            // 把新數組中的數(nums中的部分)覆蓋nums數組中的相應位置          for (int k2 = 0; k2 < temp.length; k2++) {             nums[k2 + low] = temp[k2];          }      }              // 歸并排序的實現      public static void main(String[] args) {           int[] array = {3,1,5,9};            Order.sort(array, 0, array.length-1);          System.out.PRintln(Arrays.toString(array));      }     }
8.3  性能特點
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個非常典型的應用。歸并排序的最好、最壞和平均的時間復雜度均為O(nlogn)，空間復雜度為O(n)。歸并排序比較占用內存（相對于快排的空間復雜度O(logn)以及堆排序的空間復雜度O(1)，其中三者時間復雜度相同），當n比較大的時候，歸并排序往往會出內存溢出錯誤。但卻是一種效率高且穩定的算法。