一、算法思想

? ? ? 歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個非常典型的應用，指的是將兩個已經(jīng)排序的序列合并成一個序列的操作。其歸并思想如下：

1）申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列；
2）設定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置；
3）比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置；
4）重復步驟3直到某一指針達到序列尾；
5）將另一序列剩下的所有元素直接復制到合并序列尾；

? ? ?在使用歸并排序算法的時候，算法如下：

1）將序列切分，直至切分到序列是有序的（這里通過將序列切分成單個元素達到目的）；

2）將序列塊兩兩歸并成較大的序列塊；

3）將較大的序列塊再度歸并，不斷繼續(xù)，直至歸并形成和原始序列同樣大小的序列；

?

二、算法示意圖

? ? ? 如圖所示，首先第一行表示待排序的序列，第一步就是將序列元素切割為一個個的獨立元素（表示有序序列），接著將相鄰的兩個元素按照歸并思想合并成第二行，同樣顏色的元素屬于一組，接著再次歸并，形成第三行的樣子。接著將兩組歸并，就可以形成最后一行已經(jīng)排好序的樣子。

?

三、Java代碼

1 public class MergeSort extends Sort { 2 public static void sort(int[] array) { 3 int[] tempArray = new int[array.length]; 4 mergeSort(array, tempArray, 0, array.length - 1); 5 printArray(array); 6 } 7 8 private static void mergeSort(int[] array, int[] tempArray, int left, int right ) { 9 if ( left < right ) { 10 int center = ( left + right ) / 2; 11 mergeSort(array, tempArray, left, center); 12 mergeSort(array, tempArray, center + 1, right); 13 merge(array, tempArray, left, center + 1, right); 14 } 15 } 16 17 private static void merge( int[] array, int[] tempArray, int left, int right, int end) { 18 int tempLeft = left; 19 int tempRight = right; 20 int position = left; 21 22 while(tempLeft < right && tempRight <= end){//兩個隊列都沒到頭 23 if(array[tempLeft] < array[tempRight]) 24 tempArray[position++] = array[tempLeft++]; 25 else 26 tempArray[position++] = array[tempRight++]; 27 } 28 29 while(tempLeft < right){ 30 tempArray[position++] = array[tempLeft++]; 31 } 32 33 while(tempRight <= end){ 34 tempArray[position++] = array[tempRight++]; 35 } 36 37 for(int index = left; index <= end; index++){//復制回去 38 array[index] = tempArray[index]; 39 } 40 } 41 }

算法的精華在于函數(shù)mergeSort，這是一個遞歸算法，從第9行可以看出來，數(shù)組首先被切成單個單個的元素，然后再歸并。第11~13行首先對左半部分進行歸并排序，然后對右半部分進行歸并排序，最后整體歸并。

?

四、算法復雜度

? ? ? 這里的分析和快速排序一致，同時，由于它是均分，不會出現(xiàn)和快速排序那樣分裂開來的序列不均勻導致的性能差異。我們由函數(shù)mergeSort可知，T(n)=O(nlogn)。

? ? ? 由上面的實現(xiàn)代碼可知，其空間復雜度為O(n)。我們只需要一個臨時數(shù)組在合并的時候保存數(shù)據(jù)即可。

?

?

?

轉載于:https://www.cnblogs.com/lqminn/p/3650223.html

《新程序員》：云原生和全面數(shù)字化實踐50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的【DS】排序算法之归并排序（Merge Sort）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。