波斯马BOSSMA Information Technology

c#排序算法之归并排序

发布时间:2010年9月14日 / 分类:DOTNET / 6,945 次浏览 / 评论

归并(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];
            }
        }

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

本博客所有文章如无特别注明均为原创。
复制或转载请以超链接形式注明转自波斯马,原文地址《c#排序算法之归并排序

关键字:

建议订阅本站,及时阅读最新文章!
【上一篇】 【下一篇】

发表评论