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

一、实现思路

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

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

为了更直观的理解其思路，举个更具体的例子，假设有数组{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];
    //初始化段长为1
    int 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++;
            }
        }
    }
}

循环实现是一种自下而上的求解思路，先着眼于解决最小的分片，再将其逐渐合成为大的分片。

其初始化段长为1，即一开始将数组的每个元素都视为单个有序的元素，循环中进行两次MergePass操作，是为了高效率的交替使用两个数组，这比循环实现的拷贝效率更高，同时也是为了保证最终的结果是写入到原始数组中的。

在MergePass中，将数组有序分段从左到右两两归并，每次归并同样使用Merge操作进行，并不断步进直到剩余长度不足一次步进时停止。最后单独对尾部元素处理，超过一个段长的同样使用Merge操作归并，否则直接并入数组的末尾。

三、复杂度分析

分析其过程，一趟归并需要将待排序列中所有记录扫描一遍，因此耗费O(n)时间,而由完全二叉树的深度可知，整个归并排序需要进行log₂n次，因此，总的时间复杂度为O(nlogn)，而且这是归并排序算法中最好、最坏、平均的时间性能。

由于归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结
果以及递归时深度为log2n的栈空间，因此空间复杂度为O(n+logn)。

总结

归并排序是一种比较占用内存，但却效率高且稳定的算法。非递归的迭代方法，避免了递归时深度为log2n的栈空间，空间只是用到申请归并临时用的TR数组，因此空间复杂度为O(n)，并且避免递归也在时间性能上有一定的提升，应该说，使用归并排序时，尽量考虑用非递归方法。