c# 归并排序,递归实现和非递归实现

归并排序的策略是建立在对两个有序数列合并的基础上的:

先看看怎样对两个有序的数列合并:(left~center有序,center+1~rightEnd有序)

主要采用双游标法:

        private static void MergeSorted(int[] nums,int left,int center,int rightEnd)
        {
            int right = center + 1;
            int tempPoint = 0;
            int[] tempList = new int[rightEnd - left + 1];
            while (left <= center && right <= rightEnd)
            {
                if (nums[left] <= nums[right])
                {
                    tempList[tempPoint++] = nums[left++];
                }
                else
                    tempList[tempPoint++] = nums[right++];
            }
            while (left <= center)
            {
                tempList[tempPoint++] = nums[left++];
            }
            while (right <= rightEnd)
            {
                tempList[tempPoint++] = nums[right++];
            }
            //再给nums重新赋值;
            tempPoint--;
            while(tempPoint>=0)
            {
                nums[rightEnd--] = tempList[tempPoint--];
            }            
        }

有了这个工具就很容易实现递归实现了,递归基是数组中仅有一个元素,什么操作都不用做,故此可省略

然后尽量将数组长度尽量均分,尽快缩小问题规模,分而治之,分别处理好规模较小的问题后,就是调用上述合并方法.

        private static void m_Merge_Sort(int[] nums,int start,int end)
        {
            if (start != end)
            {
                int center = (start + end) / 2;
                m_Merge_Sort(nums, start, center);
                m_Merge_Sort(nums, center + 1, end);
                MergeSorted(nums, start, center, end);
            }
        }
        public static void Merge_Sort(int[] nums)
        {
            int end = nums.Length - 1;
            m_Merge_Sort(nums, 0, end);
        }

非递归实现策略:

递归实现的思路是通常是自顶而下,非递归实现的思路就是自底而上:

先将数列看成长度为1的n个有序数列,两两合并成长度为2的n/2个,再两两合并成长度为4的,n/4个...

值得注意的是细节,数列个数并不总是是2^n,最后那个或者最后两个数列需要单独考虑.

 private static void Merge_Pass(int[] nums,int stepLength)
        {
            int numsLength = nums.Count();
            int i = 0;
            while(i <=numsLength - 2 * stepLength)
            {
                MergeSorted(nums, i, i + stepLength - 1, i + 2 * stepLength - 1);
                i += 2 * stepLength;
            }//注意跳出循环后,i是最后一个合法值+2*stepLength.
            //判断剩下的数字是否够分成两个有序数组
            if (numsLength - i  > stepLength)//说明剩下的数字个数能够分成两个有序数列
                MergeSorted(nums, i, i +  stepLength - 1, numsLength - 1);
        }
        public static void NoRecursionMerge_Sort(int[] nums)
        {
            int step = 1;
            while (step <nums.Length)
            {
                Merge_Pass(nums, step);
                step *= 2;
            }
        }