今天我們的目標(biāo)是：歸并排序。要理解這種排序，首先我們先了解一下歸并：
歸并：
現(xiàn)在我們要求將兩個(gè)從小到大排列的有序數(shù)組歸并為一個(gè)從小到大排序的有序數(shù)組。想想怎么辦呕屎？常規(guī)做法就是：
1、 創(chuàng)建一個(gè)新數(shù)組敬察，長(zhǎng)度是兩個(gè)數(shù)組的長(zhǎng)度之和秀睛。
2、 運(yùn)用三個(gè)指針莲祸，分別指向三個(gè)數(shù)組的頭部蹂安，然后比較需要?dú)w并的數(shù)組兩個(gè)指針指向的數(shù)字，得到較小者锐帜，將較小者放在新數(shù)組指針指向的位置田盈，然后向后移動(dòng)較小者數(shù)組指針，和新數(shù)組指針缴阎。
3允瞧、 重復(fù)步驟2，直到一個(gè)數(shù)組比較完畢。將未排完數(shù)組述暂，后續(xù)的數(shù)字排到新數(shù)組的尾部痹升。歸并結(jié)束。
代碼：
public static int[] Merge(int[] arr1, int[] arr2)
{
int length1 = arr1.Length;
int length2 = arr2.Length;
int[] arr = new int[length1 + length2];
int index = 0;
int i = 0;
int j = 0;
//從前往后比較兩個(gè)數(shù)組的值畦韭，誰(shuí)小疼蛾，誰(shuí)放在新數(shù)組前面
//直到一個(gè)數(shù)組比較完畢
while (i < length1 && j < length2)
{
if (arr1[i] <= arr2[j])
{
arr[index] = arr1[i];
i++;
index++;
}
else
{
arr[index] = arr2[j];
j++;
index++;
}
}
//將還沒(méi)有比較的數(shù)依次放在新數(shù)組后面
while (i < length1)
{
arr[index] = arr1[i];
i++;
index++;
}
while (j < length2)
{
arr[index] = arr2[j];
j++;
index++;
}
return arr;
}
時(shí)間復(fù)雜度： 可以看到歸并運(yùn)行的次數(shù)為( length1+length2 )次，因此它的時(shí)間復(fù)雜度為：O（n）艺配。
空間復(fù)雜度： O( n ) 察郁。
歸并排序：
歸并排序正是利用了上述歸并的思路為核心的排序方法。假設(shè)這里有一個(gè)長(zhǎng)度為1的數(shù)組转唉，那么無(wú)論如何他就是一個(gè)有序數(shù)組皮钠。歸并排序就是不斷分解數(shù)組，直到數(shù)組長(zhǎng)度為1赠法，然后不斷歸并鳞芙，最后形成一個(gè)有序的數(shù)組。這種思路就是歸并排序的遞歸實(shí)現(xiàn)的思路期虾。
演示動(dòng)畫如下：
實(shí)現(xiàn)方式有兩種：遞歸和非遞歸。
遞歸方式就是不斷拆分?jǐn)?shù)組驯嘱，直到數(shù)組長(zhǎng)度為1镶苞，然后不斷歸并。
代碼如下：
public static void MergeSort(int[] arr)
{
int length = arr.Length;
if (length<2)
{
return;
}
MegerSort(arr, 0, length-1);
}
public static void MergeSort(int[] arr,int left,int right)
{
//數(shù)組一分為2鞠评，不斷拆分茂蚓，直到數(shù)組長(zhǎng)度為1，直接返回
if (left>= right)
{
return;
}
int mid = left+(right - left) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid+1, right);
//按mid將數(shù)組分組剃幌，然后將兩組數(shù)據(jù)歸并為1組
int[] arr2 = new int[right - left+1];
int index = 0;
int i = left;
int j = mid + 1;
while (i <= mid&& j <= right)
{
if (arr[i] <= arr[j])
{
arr2[index] = arr[i];
i++;
index++;
}
else
{
arr2[index] = arr[j];
j++;
index++;
}
}
while (i <= mid)
{
arr2[index] = arr[i];
i++;
index++;
}
while (j <= right)
{
arr2[index] = arr[j];
j++;
index++;
}
for (int n = 0; n < index; n++)
{
arr[left + n] = arr2[n];
}
}
非遞歸方式就是利用循環(huán)聋涨，從按長(zhǎng)度為1分組，然后歸并负乡，不斷翻倍數(shù)組長(zhǎng)度牍白，進(jìn)行歸并。
代碼如下：
public static void MergeSort2(int[] arr)
{
int length = arr.Length;
if (length<2)
{
return;
}
//按gap對(duì)數(shù)組進(jìn)行分組抖棘，并在組內(nèi)進(jìn)行歸并
int gap = 1;
while (gap<=length)
{
int i = 0;
int left = i * (gap * 2);
while (left< length)
{
int right = (i + 1) * (gap * 2) - 1;
//數(shù)組數(shù)組越界的情況
if (right >= length)
{
right = length - 1;
}
MergeSort2(arr, left, right);
i++;
left = i * (gap * 2);
}
gap *= 2;
}
}
//將數(shù)組分組為left-mid,mid+1-right兩組進(jìn)行歸并
public static void MergeSort2(int[] arr,int left,int right)
{
if (right<= left)
{
return;
}
int mid = left + (right - left) / 2;
int[] arr2 = new int[right - left + 1];
int index = 0;
int i = left;
int j = mid + 1;
while (i <= mid && j <= right)
{
if (arr[i] <= arr[j])
{
arr2[index] = arr[i];
i++;
index++;
}
else
{
arr2[index] = arr[j];
j++;
index++;
}
}
while (i <= mid)
{
arr2[index] = arr[i];
i++;
index++;
}
while (j <= right)
{
arr2[index] = arr[j];
j++;
index++;
}
for (int n = 0; n < index; n++)
{
arr[left + n] = arr2[n];
}
}
時(shí)間復(fù)雜度：歸并一次的時(shí)間復(fù)雜度為O（n）茂腥，無(wú)論是遞歸，還是循環(huán)切省，都要執(zhí)行l(wèi)og2n次歸并最岗。因此復(fù)雜度為：O（nlog2n）
空間復(fù)雜度：O(n)。
穩(wěn)定性：穩(wěn)定排序朝捆。
