#歸并排序： --- * 背景介紹： 是創建在歸并操作上的一種有效的排序算法，效率為O(n log n)。1945年由約翰·馮·諾伊曼首次提出。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞歸可以同時進行。 ----- 來自 [wikipedia](https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F) * **算法規則： 像快速排序一樣，由于歸并排序也是分治算法，因此可使用分治思想：**<br> 1.申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列<br> 2.設定兩個指針，最初位置分別為兩個已經排序序列的起始位置 <br> 3.比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置 <br> 4.重復步驟3直到某一指針到達序列尾 <br> 5.將另一序列剩下的所有元素直接復制到合并序列尾 * 代碼實現（Java版本） public void mergeSort(int[] ints, int[] merge, int start, int end) { if (start >= end) return; int mid = (end + start) >> 1; mergeSort(ints, merge, start, mid); mergeSort(ints, merge, mid + 1, end); merge(ints, merge, start, end, mid); } private void merge(int[] a, int[] merge, int start, int end,int mid) { int i = start; int j = mid+1; int pos = start; while( i <= mid || j <= end ){ if( i > mid ){ while( j <= end ) merge[pos++] = a[j++]; break; } if( j > end ){ while( i <= mid ) merge[pos++] = a[i++]; break; } merge[pos++] = a[i] >= a[j] ? a[j++] : a[i++]; } for (pos = start; pos <= end; pos++) a[pos] = merge[pos]; }