归并排序
定义:将2个以及2个以上的有序表组合成一个新的有序表。（这里按照升序）
如上图数组arr分成了2个有序表，分别是{2,3,4,8}和{1,4,5,7} ：首先2和1比，1小，所以i++,1放入新数组temp中，i指向4,4大于2,2放入temp中，l++，指向3,3和4比，3小，所以3放在2后面，l指向6,6和4比，4小，所以4放入temp中，i指向5，同理5放入temp中，6和7比，6小，所以将6放入temp中，j++。注意此时j已经超出第二个有序子表的索引范围了，所以将第一个有序字表中剩下的值全部放入temp中，正好此时就剩下了8.
下面代码演示上述过程，只是针对于2个有序字表并且2个有序字表都是有序的情况：
class MergeSort { public static void Sort(int[] arr) { int n = arr.Length; int[] temp = new int[n]; Sort(arr, temp, 0, n - 1); } public static void Sort(int[] arr, int[] temp, int l, int r) { int mid = l + (r - l) / 2; Merge(arr, temp, l, mid, r); } /// <summary> /// 归并排序 /// </summary> /// <param name="arr"></param> /// <param name="temp"></param> /// <param name="l">数组头部索引值</param> /// <param name="mid">数组中间索引值</param> /// <param name="r">数组头部索引值</param> private static void Merge(int[] arr, int[] temp, int l, int mid, int r) { int i = l; int j = mid + 1; int k = l;//新数组开始索引值 //左右半边都还有元素 while (i <= mid && j <= r) { if (arr[i] < arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } //如果左半边还有元素，将左半边元素全部放入到新数组中 while (i <= mid) temp[k++] = arr[i++]; //如果右半边还有元素，将右半边元素全部放入到新数组中 while (j<= r) temp[k++] = arr[j++]; //将数组拷贝到原数组 for (int z = l; z <= r; z++) { arr[z] = temp[z]; } } }
调用：
static void Main(string[] args) { int[] arr = { 2, 3, 6, 8,1,4,5,7}; MergeSort.Sort(arr); for (int i = 0; i < arr.Length; i++) { Console.WriteLine(arr[i]); } }
结果：
1
2
3
4
5
6
7
8
但是实际情况并不会像我们上面设计的那样下面我们来解决这个问题。
下图中可以看出，可以将含有n个元素的序列看成是由n个有序子序列组合起来的 ，每个子序列的长度为2或者1，然后再对这些子序列进行两两归并，称之为2-路归并排序。
将上面代码改为如下:
public static void Sort(int[] arr, int[] temp, int l, int r) { if (l >= r) { return; } int mid = l + (r - l) / 2; //使用递归 分别将左右两侧元素有序化 Sort(arr, temp, l, mid); Sort(arr, temp, mid + 1, r); Merge(arr, temp, l, mid, r); }
使用归并排序的时间复杂度能达到O(nlogn),对于初始数组有序性很强的数组，使用插入排序的性能更高，能达到O(n)。
优化
时间复杂度表征的是随输入数据规模的变化，其时间消耗的变化趋势，
空间复杂度则为随输入数据规模的变化，其空间消耗的变化趋势。
对于数据量较少的并且有序性高的数组可以直接使用插入排序，减少归并排序因为不断递归造成的空间消耗。
具体优化点在（1）（2）处。
class MergeSort { public static void Sort(int[] arr) { int n = arr.Length; int[] temp = new int[n]; Sort(arr, temp, 0, n - 1); } public static void Sort(int[] arr, int[] temp, int l, int r) { //(r - l + 1) 为整个数组的长度，如果长度小于15，使用 //（1）插入排序更快，因为减少了空间复杂度，归并排序需要不断递归，占用内存相对大。 if ((r - l + 1) <= 15) { //参数分别是l,r 不是数字1. InsertSort(arr, l, r); } int mid = l + (r - l) / 2; //使用递归 分别将左右两侧元素有序化 Sort(arr, temp, l, mid); Sort(arr, temp, mid + 1, r); //（2）如果左边有序子列中最大值大于右边有序子列中的最小值，说明这2个有序子列需要进行归并，合成一个有序的序列 if (arr[mid] > arr[mid + 1]) Merge(arr, temp, l, mid, r); } /// <summary> /// 归并排序 /// </summary> /// <param name="arr"></param> /// <param name="temp"></param> /// <param name="l">数组头部索引值</param> /// <param name="mid">数组中间索引值</param> /// <param name="r">数组头部索引值</param> private static void Merge(int[] arr, int[] temp, int l, int mid, int r) { int i = l; int j = mid + 1; int k = l;//新数组开始索引值 //左右半边都还有元素 while (i <= mid && j <= r) { if (arr[i] < arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } //如果左半边还有元素，将左半边元素全部放入到新数组中 while (i <= mid) temp[k++] = arr[i++]; //如果右半边还有元素，将右半边元素全部放入到新数组中 while (j <= r) temp[k++] = arr[j++]; //将数组拷贝到原数组 for (int z = l; z <= r; z++) { arr[z] = temp[z]; } } /// <summary> /// 插入排序 升序 /// </summary> /// <param name="arr"></param> public static void InsertSort(int[] arr, int l, int r) { for (int i = l + 1; i <= r; i++) { //插入元素e int e = arr[i]; //j表示元素e应该插入的位置 int j; for (j = i; j > 0; j--) { if (e < arr[j]) { arr[j] = arr[j - 1]; } else { //此时说明不用再比较了 break; } } //通过for循环判断，最终找到了j具体的位置，将元素e放在此位置上 arr[j] = e; } } }