什麼是歸併排序？
歸併排序簡單來講，就是將兩個有序的序列整合到一起。
推薦教學：PHP影片教學
#如何將兩個有順序的序列整合在一起呢？
那麼我們假設，現在有 M=｛m1 ，m2，m3，....，mx｝序列和 N = ｛n1，n2，n3，....， ny｝序列，這兩個序列已經是有序的序列，首先創建一個空序列 K = ｛｝，那麼接著將 m1 和 n1 進行比較，加入 m1 < n1 那麼將 m1 K 序列中，然後 M 序列中，然後 M1 序列遊標後移，即下次將進行 m2 和 n1 的比較，直到全部比較完畢，並填入序列 K 中。
既然歸併排序是整合有序序列，那麼豈不是不能排序無序序列，這條件也太苛刻了點吧？
歸併排序是建立在分治法的基礎上進行操作的，也就是可以將一個完全無序的序列進行無線分割以達到有序序列，例如：現在有M=｛m1 ，m2，m3，....，mx｝，M序列是完全無序的序列，那麼此時可以將 M 序列分成若干個小序列－｛m1，m2｝，｛m3，m4 ｝....｛mx-1，mx｝；此時這些序列就是有序的，那麼就可以透過歸併操作進行排序，所以歸併排序也可以排序無序序列，且速度僅次於快速排序，屬於穩定排序。
如何分割序列？
上個問題已經提過，歸併排序是建立在分治的基礎上進行操作的，其中分治的體現就體現在分割序列上，比如：現在有M =｛m1 ，m2，m3，....，mx｝，第一次分割：M1 = ｛m1，m2，...，m（x 1）/2｝，M2 = ｛m（x 1）/ 2 1，m（x 1）/2 2，...，mx｝，第一次分割之後得到 M1 和 M2 序列，然後再分割 M1 和 M2 ，分割若干次之後得到 x/2 x%2 個序列，然後再逐一進行歸併操作。
此演算法特定步驟：
1、規定首指標 left 與mid（left指向序列1的首元素，right 指向序列2的首元素）
2、比較 left 和 mid 的大小，將小的元素放入新建的空間中
3、重複步驟2，直到其中一個序列遍歷完畢
4、將剩餘的未加入新空間中的元素直接複製貼上進新空間
該演算法的核心步驟：
1、使用分治法（遞歸）分割序列
2、比較 left 和 mid 的大小， 將小的元素的添加進入新建空間
敘述完畢，貼上程式碼：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 排序__归并排序
{
class 归并
{
public static int[] arr = { 6, 202, 301, 100, 38, 8, 1 ,-1,1000};
static void Main(string[] args)
{
Sort(arr, 0, arr.Length -1);
foreach (var item in arr)
{
Console.Write(item + " ");
}
Console.ReadKey();
}
public static void Sort(int []a,int left,int right)
{
if (left >= right) return;
else
{
int mid = (left + right) / 2; //@1
Sort(a, left, mid);
Sort(a, mid + 1, right);
MergeSort(a, left, mid, right);
}
}
public static void MergeSort(int []a,int left,int mid,int right)
{
int[] Arr = new int[right - left + 1];
int l = left, m = mid +1 , k = 0; //@2
while ( m <= right && l <= mid ) //@3
{
if (a[l] > a[m]) Arr[k++] = a[m++];
else Arr[k++] = a[l++];
}
while (m < right +1) //@4
{
Arr[k++] = a[m++];
}
while (l < mid +1 ) Arr[k++] = a[l++]; //@4
for (k = 0, l = left; l < right + 1; k++, l++) a[l] = Arr[k];
}
}
}程式碼解讀：
## @1 ：Sort（）函數完成了序列的分割，每一次遞迴都會將序列分成兩半，直到無法分隔為止。 @2 ：l 代表序列1的首元素，m 代表序列2的首元素，k代表新建數組Arr的已有元素個數 @3 ：序列1的首元素和序列2的首元素進行比較，將小的放入 Arr 中，且序列遊標後移，直到其中一個序列的元素遍比較完畢 @4 ：在序列1 和序列2的比較過程中，可能出現序列1已經全部加入了 Arr 中，但是序列2還沒有，則將剩餘的未比較的元素直接複製進入 Arr 中
##總結： 以上程式碼並不是真正意義上的分割數組，只是做了一個邏輯分割，沒有像其他程式碼一樣將分割後的數組填入一個新的數組，那樣做的話會對速度和記憶體產生一點影響，雖然微乎其微，但總歸是沒這麼好的，在歸併操作上，需要注意的是參數不要越界（我當時就想了很久為什麼 @2 上面的m 要等於 mid 1 而不是 mid ，其實道理很簡單，因為mid是屬於左序列，從 mid 1 開始才屬於右序列，將m = mid 1 改成 m = mid 不是不行，只是後面的程式碼也需要改，但是沒有必要多做一次無用比較，這個問題我當時真是想了半天...），其實只要理清楚其中的邏輯關係，這樣程式碼就能做到信手拈來。
以上是排序演算法—歸併排序【附代碼】的詳細內容。更多資訊請關注PHP中文網其他相關文章！
