小小c#算法题 - 8 - 归并排序 (Merging Sort)

野性酷女 2022-01-06 12:23 225阅读 0赞

“归并”的含义是将两个或两个以上的有序序列组合成一个新的有序序列。这个“归并”可以在O(n+m)的数量级上实现，但这同时也需要O(n+m)的空间复杂度。具体为：首先分配一个新的长度为n+m的空序列，然后对于序列1（长度为n)，序列2（长度为m），从每个序列的第一个元素开始比较，将较小的元素放入新的序列，然后较小元素原来所在序列的下标加1，这样一直比较下去，最终把这两个序列有序的放入新的序列中。在2-路归并排序中，这里的序列1，序列2表现为待排序列的两个相邻子序列。

2-路归并排序的定义：假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2(上取整)个长度为2或1的有序子序列；再两两归并，......，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2-路归并排序。

那么可以看出，2-路归并排序中的核心操作是将一维数组中相邻的**两个**有序子序列归并为**一个**有序序列，代码如下：

传入一个数组，将这个数组中的两个有序子序列（low ~ middle, middle + 1 ~high)合并成一个有序的子序列。先把序列copy一份，用来后面比较元素使用。

static void Merge(int[] numbers, int low, int middle, int high)
            {
                int[] temp = new int[numbers.Length];
                numbers.CopyTo(temp, 0);
                int index = low;
                int m = middle + 1;
                while (low <= middle && m <= high)
                {
                    if (temp[low] <= temp[m])
                    {
                        numbers[index++] = temp[low++];
                    }
                    else
                    {
                        numbers[index++] = temp[m++];
                    }
                }
    
                // 比较循环结束后，左边（低位）子序列有剩余元素的情况
                while (low <= middle)
                {
                    numbers[index++] = temp[low++];
                }
    
                // 比较循环结束后，右边（高位）子序列有剩余元素的情况
                while (m <= high)
                {
                    numbers[index++] = temp[m++];
                }
            }

上面核心操作的算法已经实现了，下面就是怎么通过调用上述算法来对序列进行排序了。这里采用了递归的思想，当对一个序列进行排序时，分别对其左，右子序列进行排序（一般从中间划分），左，右子序列有序后，调用Merger方法合并这两个子序列，得到整个的有序序列。递归停止的条件是序列长度只为1的时候。代码如下：

static void MergeSort(int[] numbers, int low, int high)
            {
                // low == high时序列长度为1，是停止递归的条件
                if (low != high)
                {
                    int middle = (low + high) / 2;
                    MergeSort(numbers, low, middle);
                    MergeSort(numbers, middle + 1, high);
                    Merge(numbers, low, middle, high);
                }
            }

为了方便调用，对MergeSort又封装一次：

static void MSort(int[] numbers)
            {
                MergeSort(numbers, 0, numbers.Length - 1);
            }

下面是对MergeSort方法的调用（这个例子使用控件台应用程序类型）:

static void Main(string[] args)
            {
                int[] numbers = { 49, 38, 65, 97, 76, 13, 27, 49, 32, 100, 1, 345, 67 };
                MSort(numbers);
    
                foreach (int i in numbers)
                {
                    Console.Write(i.ToString() + " ");
                }
             }

归并排序是稳定的排序，Merge方法的时间复杂度为O(n), 要实现排序，需调用logn次Merge方法，所以归并排序的时间复杂度为O(n\*logn)。由于排序时需要额外的临时序列的copy，所以空间复杂度为O(n)，这也是归并排序的缺点。

一个可以优化的地方：

Merger方法中，每次都要copy一整份序列。但其实只要copy其中的要比较的两个子序列中的元素即可，所以有优化代码如下：

static void Merge(int[] numbers, int low, int middle, int high)
            {
                int[] temp = new int[high - low + 1];
                for (int i = low, j = 0; i <= high; i++)
                {
                    temp[j++] = numbers[i];
                }
    
                int index = low;
                middle -= low;
                high -= low;
                low = 0;
                int m = middle + 1;
                while (low <= middle && m <= high)
                {
                    if (temp[low] <= temp[m])
                    {
                        numbers[index++] = temp[low++];
                    }
                    else
                    {
                        numbers[index++] = temp[m++];
                    }
                }
    
                while (low <= middle)
                {
                    numbers[index++] = temp[low++];
                }
    
                while (m <= high)
                {
                    numbers[index++] = temp[m++];
                }
            }

转载于:https://www.cnblogs.com/CSharpSPF/p/3199679.html