1.概要
归并排序（Merge-Sort）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分（divide）成一些小的问题然后递归求解，而治（conquer）的阶段则将分的阶段得到的各答案“修补在一起，即分而治之”）。.思路1：可以看到这种结构很想一颗完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程。
思路2：合并相邻有序子序列
再来看看治阶段，我们需要两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，将要[4,5,8,7]和[1,2,3,6] 两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。
2.详细内容
public class MergeSort
{
//分+合方法
public static void Sort(int[] arr, int left, int right, int[] temp)
{
if (left < right)
{
int mid = (left + right) / 2;
//向左递归进行分解
Sort(arr,left,mid,temp);
//向右递归进行分解
Sort(arr, mid + 1, right, temp);
//每分解一次就合并一次
Merge(arr,left, mid, right, temp);
}
}
/// <summary>
/// 归并排序
/// </summary>
/// <param name="arr">排序的原始数组</param>
/// <param name="left">左边有序序列</param>
/// <param name="mid">中间索引</param>
/// <param name="right">右边有序序列</param>
/// <param name="temp">中转数组</param>
public static void Merge(int[] arr,int left,int mid,int right, int[] temp) {
int i = left;//初始化i，左边有序序列的初始索引
int j = mid + 1;//初始化j，右边有序序列的初始索引
int t = 0;//指向temp数组的当前索引
//1
//先把左右两边（有序）的数据按照规则填充到temp数组
//直到左右两边有序序列，又一遍处理完毕为止
while (i <= mid && j <= right) {
//如果左边的有序序列的当前元素，小于等于邮编的有序序列的当前元素
//即将左边的当前元素，拷贝到temp数组
//然后t++ i++
if (arr[i] <= arr[j])
{
temp[t] = arr[i];
t += 1;
i += 1;
}
else
{
//如果右边的有序序列的当前元素，大于邮编的有序序列的当前元素
//即将右边的当前元素，拷贝到temp数组
//然后t++ j++
temp[t] = arr[j];
t += 1;
j += 1;
}
}
//2
//把有剩余数据的一遍的数据一次全部填充到temp
while (i<=mid)
{
//左边的有序序列还有剩余的元素，就全部填充到temp
temp[t] = arr[i];
t += 1;
i += 1;
}
while (j <= right)
{
//右边的有序序列还有剩余的元素，就全部填充到temp
temp[t] = arr[j];
t += 1;
j += 1;
}
//3
//将temp数组的元素拷贝到arr
t = 0;
int tempLeft = left;
while (tempLeft <= right)
{
//第一次合并tempLeft = 0，right = 1 tempLeft = 2 right=3 t=0 tL=0 ri=3
//最后一次tempLeft=0 right=7
arr[tempLeft] = temp[t];
t += 1;
tempLeft += 1;
}
}
}
static void Main(string[] args)
{
int[] array = { 8,4,5,7,1,3,6,2 };
//归并排序需要一个额外的空间
int[] temp =new int[array.Length];
MergeSort.Sort(array,0,array.Length - 1, temp);
Console.WriteLine(string.Join(' ', array));
Console.Read();
}
