排序算法——归并排序（三）

文章目录

一、实现思路
二、代码实现
三、复杂度分析
总结

一、实现思路

归并排序是使用分治思想解决问题的典型算法，对于一个庞大的乱序数组我们很难针对整体对其进行排序，但是对于微小的数组却很容易对其进行排序，有了数个有序的小数组，对其进行整体排序也就更加容易。

比如我们很难对全省的高考考生成绩看作一个集合来进行整体排序，但是将考生划分到每个省、每个市、每个学校、每个班级再对其排名则要容易的多，有了班级排名，就可以很容易得到全校排名，有了校排名就可以得到市排名等等。

为了更直观的理解其思路，举个更具体的例子，假设有数组{16,7,13,10,9,15,3,2,5,8,12,1,11,4,6,14}，对其进行归并排序的过程如下所示：
在这里插入图片描述
可以看到其像一颗倒置的完全二叉树。通常涉及二叉树的算法，效率都不会太低。

“归并”一词的中文含义就是合并、并入的意思，而在数据结构中的定义是将两个或两个以上的有序表组合成一个新的有序表。

归并排序就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。

二、代码实现

public static void MergeSortRecursion(int[] arr)
{if (arr.Length < 0 || arr == null){return;}//创建交换数组int[] arrTemp = new int[arr.Length];_MergeSort(0, arr.Length - 1, arr, arrTemp);void _MergeSort(int left, int right, int[] source, int[] dest){if (right == left){return;}int mid = (left + right) / 2;//递归处理左侧_MergeSort(left, mid, source, dest);//递归处理右侧_MergeSort(mid + 1, right, source, dest);//对结果合并Merge(left, mid, right, source, dest);}void Merge(int left, int mid, int right, int[] source, int[] dest){int curIndex = left;int leftPtr = left;int rightPtr = mid + 1;//当左右两分段都有数据，归并排序while (leftPtr <= mid && rightPtr <= right){if (source[leftPtr] <= source[rightPtr]){dest[curIndex] = source[leftPtr];leftPtr++;}else{dest[curIndex] = source[rightPtr];rightPtr++;}curIndex++;}//处理剩余数据if (leftPtr <= mid){while (leftPtr <= mid){dest[curIndex] = source[leftPtr];leftPtr++;curIndex++;}}else if (rightPtr <= right){while (rightPtr <= right){dest[curIndex] = source[rightPtr];rightPtr++;curIndex++;}}//将排序好的数组拷贝回原数组Array.Copy(dest, left, source, left, right - left + 1);}
}

首先创建一个交换数组，这个数组是用于数据交换的，整个排序过程中数据会在原始数组与交换数组之间来回倒换。

在_MergeSort方法中对当前的数组分段一切为2，左右递归的进行处理，这是一种自上而下的求解思路，我们假设递归处理已经正确的处理了结果，之后再对得到的有序的左右两个分段进行合并成为一个分段，该递归的跳出条件为left==right，意味着递归已经到达了递归树的底端，不可再切分，此时分片足够小可对其直接处理。

核心是Merge方法，它将两个有序的数组合并为一个有序数组，其思路也很明了，最后一定要记得将归并好的结果倒回原始数组中，不然下次递归会使用错误的结果。

上述是归并排序的递归实现，虽然逻辑清晰实现简单容易理解，但存在一定的性能问题（递归开销以及数组的冗余拷贝开销），有没有更加高效的实现？当然是有的，以下是归并排序的循环实现：

public static void MergeSort(int[] arr)
{if (arr.Length < 0 || arr == null){return;}//创建交换数组int[] arrTemp = new int[arr.Length];//初始化段长为1int curPassLength = 1;while (curPassLength < arr.Length){MergePass(arr, arrTemp, curPassLength);curPassLength *= 2;MergePass(arrTemp, arr, curPassLength);curPassLength *= 2;}//合并段落void MergePass(int[] source, int[] dest, int passLength){int curIndex = 0;//当前处理到的索引int stepLength = 2 * passLength;//步进长度//当剩余待排序表长度足够步进一次时while (curIndex + stepLength - 1 <= source.Length - 1){Merge(curIndex, curIndex + passLength - 1, curIndex + stepLength - 1, source, dest);curIndex += stepLength;}//处理不足一次步进的情况//若剩余长度大于一个段长if (curIndex + passLength <= source.Length - 1){Merge(curIndex, curIndex + passLength - 1, source.Length - 1, source, dest);}//若剩余长度小于一个段长else{while (curIndex < source.Length){dest[curIndex] = source[curIndex];curIndex++;}}}//对两个分段进行合并void Merge(int left, int mid, int right, int[] source, int[] dest){int curIndex = left;int leftPtr = left;int rightPtr = mid + 1;//当左右两分段都有数据，归并排序while (leftPtr <= mid && rightPtr <= right){if (source[leftPtr] <= source[rightPtr]){dest[curIndex] = source[leftPtr];leftPtr++;}else{dest[curIndex] = source[rightPtr];rightPtr++;}curIndex++;}//处理剩余数据if (leftPtr <= mid){while (leftPtr <= mid){dest[curIndex] = source[leftPtr];leftPtr++;curIndex++;}}else if (rightPtr <= right){while (rightPtr <= right){dest[curIndex] = source[rightPtr];rightPtr++;curIndex++;}}}
}