c#排序算法之归并排序

发布时间：2010年9月14日 / 分类：DOTNET / 8,090 次浏览 / 评论

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并操作的工作原理如下：
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

/// <summary>
        /// 归并排序
        /// </summary>
        /// <param name="intArr"></param>
        static void MergeSort(int[] intArr)
        {
            //统计比较和交换次数
            int numberOfLoop = 0;
            int numberOfSwap = 0;

            int[] tempArr = new int[intArr.Length];
            MergeAdjust(tempArr,ref intArr, 0, intArr.Length - 1, ref numberOfLoop, ref numberOfSwap);

            DisplaySortResult(numberOfLoop, numberOfSwap, intArr);
        }

        /// <summary>
        /// 递归调用归并
        /// </summary>
        /// <param name="tempArr"></param>
        /// <param name="intArr"></param>
        /// <param name="left"></param>
        /// <param name="right"></param>
        /// <param name="numberOfLoop"></param>
        /// <param name="numberOfSwap"></param>
        private static void MergeAdjust(int[] tempArr, ref int[] intArr, int left, int right, ref int numberOfLoop, ref int numberOfSwap)
        {
            if (left != right)
            {
                int middle = (left + right) / 2;

                //递归，继续细分数组，最后比较相邻的两个元素
                MergeAdjust(tempArr, ref intArr, left, middle, ref numberOfLoop, ref numberOfSwap);
                MergeAdjust(tempArr, ref intArr, middle + 1, right, ref numberOfLoop, ref numberOfSwap);
                //归并
                Merge(tempArr, ref intArr, left, middle + 1, right, ref numberOfLoop, ref numberOfSwap);
            }
        }

        /// <summary>
        /// 归并操作
        /// </summary>
        /// <param name="tempArr"></param>
        /// <param name="intArr"></param>
        /// <param name="left"></param>
        /// <param name="rl"></param>
        /// <param name="right"></param>
        /// <param name="numberOfLoop"></param>
        /// <param name="numberOfSwap"></param>
        private static void Merge(int[] tempArr, ref int[] intArr, int left, int rl, int right, ref int numberOfLoop, ref int numberOfSwap)
        {
            int ll = left;//数组一左侧
            int lr = rl - 1;//数组一右侧

            int i = 0;
            while (ll <= lr && rl <= right)
            {
                numberOfLoop++;
                numberOfSwap++;

                //两个数组比较，将小的先插入
                if (intArr[ll] < intArr[rl])
                {
                    tempArr[i] = intArr[ll];
                    ll++;
                }
                else
                {
                    tempArr[i] = intArr[rl];
                    rl++;
                }
                i++;
            }

            //上边对数组进行归并后，可能有一个数组会有剩余的元素
            //拷贝数组一剩余的部分到临时数组
            while (ll <= lr)
            {
                numberOfLoop++;
                numberOfSwap++;

                tempArr[i] = intArr[ll];
                ll++;
                i++;
            }

            //拷贝数组二剩余的部分到临时数组
            while (rl <= right)
            {
                numberOfLoop++;
                numberOfSwap++;

                tempArr[i] = intArr[rl];
                rl++;
                i++;
            }

            //将有序数据更新到数组中
            for (int j = 0; j <= i-1; j++)
            {
                numberOfSwap++;
                intArr[left + j] = tempArr[j];
            }
        }

运行效率和快速排序、堆排序差不多：