歸并排序（Merge sort），是創(chuàng)建在歸并操作上的一種有效的排序算法，效率為O(nlog n)。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞歸可以同時進行。

一、算法基本思想

（1）基本思想

歸并排序的基本思想就是：把待排序序列分為若干個子序列，每個子序列是有序的，然后再把有序子序列合并為整體有序序列。經(jīng)常被使用的是二路歸并算法，即將兩個已經(jīng)排序的序列合并成一個序列的操作。

（2）運行過程

歸并排序算法的運行過程如下：

1、申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列；

2、設定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置；

3、比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置；

4、重復步驟3直到某一指針達到序列尾；

5、將另一序列剩下的所有元素直接復制到合并序列尾。

（3）示例

二、算法實現(xiàn)（核心代碼）

C++實現(xiàn)：

template<typename T> //整數(shù)或浮點數(shù)皆可使用 void merge_sort(T arr[], int len) {T* a = arr;T* b = new T[len];for (int seg = 1; seg < len; seg += seg) {for (int start = 0; start < len; start += seg + seg) {int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);int k = low;int start1 = low, end1 = mid;int start2 = mid, end2 = high;while (start1 < end1 && start2 < end2)b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];while (start1 < end1)b[k++] = a[start1++];while (start2 < end2)b[k++] = a[start2++];}T* temp = a;a = b;b = temp;}if (a != arr) {for (int i = 0; i < len; i++)b[i] = a[i];b = a;}delete[] b; }

Java實現(xiàn)：

public void merge_sort(int[] arr) {int len = arr.length;int[] result = new int[len];int block, start;for(block = 1; block < len ; block *= 2) {for(start = 0; start <len; start += 2 * block) {int low = start;int mid = (start + block) < len ? (start + block) : len;int high = (start + 2 * block) < len ? (start + 2 * block) : len;//兩個塊的起始下標及結(jié)束下標int start1 = low, end1 = mid;int start2 = mid, end2 = high;//開始對兩個block進行歸并排序while (start1 < end1 && start2 < end2) {result[low++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];}while(start1 < end1) {result[low++] = arr[start1++];}while(start2 < end2) {result[low++] = arr[start2++];}}int[] temp = arr;arr = result;result = temp;}result = arr; }

三、性能（算法時間、空間復雜度、穩(wěn)定性）分析

歸并排序的時間復雜度為O(nlogn)；空間復雜度為O(n)；是穩(wěn)定的排序算法。

歸并排序速度僅次于快速排序，為穩(wěn)定排序算法。一般用于對總體無序，但是各子項相對有序的數(shù)列效果比較好。

總結(jié)

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

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