C#归并排序的实现方法(递归,非递归,自然归并)

//Main:

代码如下:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Merge
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                Console.WriteLine("请选择:");
                Console.WriteLine("1.归并排序(非递归)");
                Console.WriteLine("2.归并排序(递归)");
                Console.WriteLine("3.归并排序(自然合并)");
                Console.WriteLine("4.退出");
                int Arraynum = Convert.ToInt32(Console.ReadLine());
                switch (Arraynum)
                {
                    case 4:
                        Environment.Exit(0);
                        break;
                    case 1:
                        Console.WriteLine("Please Input Array Length");
                        int Leng271 = Convert.ToInt32(Console.ReadLine());
                        Function obj1 = new Function(Leng271);

Console.WriteLine("The original sequence:");
                        Console.WriteLine(obj1);
                        Console.WriteLine("'MergeSort' Finaly Sorting Result:");
                        obj1.ToMergeSort();
                        Console.WriteLine(obj1);
                        break;
                    case 2:
                        Console.WriteLine("Please Input Array Length");
                        int Leng272 = Convert.ToInt32(Console.ReadLine());
                        Function obj2 = new Function(Leng272);

Console.WriteLine("The original sequence:");
                        Console.WriteLine(obj2);
                        Console.WriteLine("'RecursiveMergeSort' Finaly Sorting Result:");
                        obj2.ToRecursiveMergeSort();
                        Console.WriteLine(obj2);
                        break;
                    case 3:
                        Console.WriteLine("Please Input Array Length");
                        int Leng273 = Convert.ToInt32(Console.ReadLine());
                        Function obj3 = new Function(Leng273);

Console.WriteLine("The original sequence:");
                        Console.WriteLine(obj3);
                        obj3.ToNaturalMergeSort();
                        Console.WriteLine();Console.WriteLine();
                        Console.WriteLine("'NaturalMergeSort' Finaly Sorting Result:");
                        Console.WriteLine(obj3);
                        break;
                }
            }
        }
    }
}

//Class:

代码如下:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Merge
{
    // 【example 2.7】//抱歉,实在不知怎么学习英语,语法什么错误之处还请见谅。
    class Function
    {
        private int Groups;
        private int CopyGroups;
        private int mergerows;
        private int[] Array27;
        private static Random ran = new Random();
        public Function(int length)
        {
            Array27 = new int[length];
            for (int i = 0; i < length; i++)
                Array27[i] = /*Convert.ToInt32(Console.ReadLine()); //*/ran.Next(1, 100);
        }
        //选择
        public void ToMergeSort()
        {
            MergeSort(Array27);
        }
        public void ToRecursiveMergeSort()
        {
            RecursiveMergeSort(Array27, 0, Array27.Length - 1);
        }
        public void ToNaturalMergeSort()
        {
            NaturalMergeSort(Array27);
        }

/// <summary>
        /// 归并排序(递归)
        ///    核心思想:(分治)
        ///           将待排序元素(递归直至元素个数为1)分成左右两个大小大致相同的2个子集合,然后,
        ///           分别对2个子集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合. 
        /// 核心算法时间复杂度:  
        ///           T(n)=O(nlogn)
        /// 参考 优秀代码: http://zh.wikipedia.org/wiki/%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F
        ///               http://www.cnblogs.com/mingmingruyuedlut/archive/2011/08/18/2144984.html
        /// </summary>
        /// <param name="Array"></param>
        /// <param name="left"></param>
        /// <param name="right"></param>
        public void RecursiveMergeSort(int[] Array, int left, int right)
        {
            int middle = (left + right) / 2;

if (left < right)
            {
                //对前半部分递归拆分
                RecursiveMergeSort(Array, left, middle);
                //对后半部分递归拆分
                RecursiveMergeSort(Array, middle + 1, right);
                MergeOne(Array, left, middle, right);
            }
        }
        public void MergeOne(int[] Array, int left, int middle, int right)
        {
            int leftindex = left;
            int rightindex = middle + 1;
            //动态临时二维数组存放分割为两个小Array的数组排列顺序后的数据
            int[] merge = new int[right + 1];
            int index = 0;
            //对两个小数组合并排序
            while (leftindex <= middle && rightindex <= right)
                merge[index++] = (Array[leftindex] - Array[rightindex]) >= 0 ? Array[rightindex++] : Array[leftindex++];
            //有一侧子数列遍历完后,将另外一侧子数列剩下的数依次放入暂存数组中(有序)
            if (leftindex <= middle)
            {
                for (int i = leftindex; i <= middle; i++)
                    merge[index++] = Array[i];
            }
            if (rightindex <= right)
            {
                for (int i = rightindex; i <= right; i++)
                    merge[index++] = Array[i];
            }
            //将有序的数列 写入目标数组 ,即原来把Array数组分为两个小Array数组后重新有序组合起来(覆盖原数组)
            index = 0;
            for (int i = left; i <= right; i++)
                Array[i] = merge[index++];
        }

/// <summary>
        /// 归并排序(非递归)
        ///     核心思想:(分治)
        ///           对n个数的数列每相邻两个元素排序,组成n/2个或(n+1)/2个子数组,单个的不比了直接进入下一轮。
        ///     然后对每个相邻的子数组再排序,以此类推最后得到排好序的数列
        ///  forexample:  59 35 54 28 52
        ///   排序And分:  35 59. 28 54. 52
        ///   排序And分:  28 35 54 59. 52
        ///        结果:  28 35 52 54 59
        /// 核心算法时间复杂度:  
        ///           T(n)=O(nlogn)
        /// </summary>
        /// <param name="Array"></param>
        public void MergeSort(int[] Array)
        {
            //index固定的数组
            int[] merge = new int[Array.Length];
            int P = 0;
            while (true)
            {
                int index = 0;
                //子数组元素的个数
                int ENumb = (int)Math.Pow(2, P);
                //一个子数组中的元素个数与数组的一半元素个数比较大小
                //最糟糕的情况最右边的数组只有一个元素
                if (ENumb < Array.Length)
                {
                    while (true)
                    {
                        int TorFAndrightindex = index;
                        //最后一个子数组的第一个元素的index与数组index相比较
                        if (TorFAndrightindex <= Array.Length - 1)
                            MergeTwo(Array, merge, index, ENumb);
                        else
                            break;
                        index += 2 * ENumb;
                    }
                }
                else
                    break;
                P++;
            }
        }
        public void MergeTwo(int[] Array, int[] merge, int index, int ENumb)
        {
            //换分两个子数组的index(千万不能用middle = (right + left) / 2划分)
            // 1
            int left = index;
            int middle = left + ENumb - 1;
            //(奇数时)
            //排除middleindex越界
            if (middle >= Array.Length)
            {
                middle = index;
            }
            //同步化merge数组的index
            int mergeindex = index;
            // 2
            int right;
            int middleTwo = (index + ENumb - 1) + 1;
            right = index + ENumb + ENumb - 1;
            //排除最后一个子数组的index越界.
            if (right >= Array.Length - 1)
            {
                right = Array.Length - 1;
            }
            //排序两个子数组并复制到merge数组
            while (left <= middle && middleTwo <= right)
            {
                merge[mergeindex++] = Array[left] >= Array[middleTwo] ? Array[middleTwo++] : Array[left++];
            }
            //两个子数组中其中一个比较完了(Array[middleTwo++] 或Array[left++]),
            //把其中一个数组中剩下的元素复制进merge数组。
            if (left <= middle)
            {
                //排除空元素.
                while (left <= middle && mergeindex < merge.Length)
                    merge[mergeindex++] = Array[left++];
            }
            if (middleTwo <= right)
            {
                while (middleTwo <= right)
                    merge[mergeindex++] = Array[middleTwo++];
            }
            //判断是否合并至最后一个子数组了
            if (right + 1 >= Array.Length)
                Copy(Array, merge);
        }

/// <summary>
        /// 自然归并排序:
        ///      对于初始给定的数组,通常存在多个长度大于1的已自然排好序的子数组段.
        /// 例如,若数组a中元素为{4,8,3,7,1,5,6,2},则自然排好序的子数组段
        /// 有{4,8},{3,7},{1,5,6},{2}.
        /// 用一次对数组a的线性扫描就足以找出所有这些排好序的子数组段.
        /// 然后将相邻的排好序的子数组段两两合并,
        /// 构成更大的排好序的子数组段({3,4,7,8},{1,2,5,6}).
        /// 继续合并相邻排好序的子数组段,直至整个数组已排好序.
        /// 核心算法时间复杂度:
        ///        T(n)=○(n);
        /// </summary>
        public void NaturalMergeSort(int[] Array)
        {
            //得到自然划分后的数组的index组(每行为一个自然子数组)
            int[,] PointsSymbol = LinearPoints(Array);
            //子数组只有一个。
            if (PointsSymbol[0, 1] == Array.Length - 1)
                return;
            //多个(至少两个子数组)...
            else
                //可以堆栈调用吗?
                NaturalMerge(Array, PointsSymbol);

}
        public void NaturalMerge(int[] Array, int[,] PointsSymbol)
        {
            int left;
            int right;
            int leftend;
            int rightend;

mergerows = GNumberTwo(Groups);
            CopyGroups = Groups;
            //固定状态
            int[] TempArray = new int[Array.Length];
            //循环取每个自然子数组的index
            while (true)
            {
                // int Temprow = 1;
                //只记录合并后的子数组(”《应该为》“动态的) 
                int[,] TempPointsSymbol = new int[mergerows, 2];

int row = 0;
                do
                {
                    //最重要的判断:最后(一组子数组)是否可配对
                    if (row != CopyGroups - 1)
                    { //以上条件也可以含有(& 和&&的区别)短路运算
                        //参考:http://msdn.microsoft.com/zh-cn/library/2a723cdk(VS.80).aspx
                        left = PointsSymbol[row, 0];
                        leftend = PointsSymbol[row, 1];
                        right = PointsSymbol[row + 1, 0];
                        rightend = PointsSymbol[row + 1, 1];
                        MergeThree(Array, TempArray, left, leftend, right, rightend);
                        MergePointSymbol(PointsSymbol, TempPointsSymbol, row);
                    }
                    else
                    {
                        ////默认剩下的单独一个子数组已经虚拟合并。然后Copy进TempArray。
                        int TempRow = PointsSymbol[row, 0];
                        int TempCol = PointsSymbol[row, 1];
                        while (TempRow <= TempCol)
                            TempArray[TempRow] = Array[TempRow++];
                        //TempPointSymbol完整同步
                        TempPointsSymbol[row / 2, 0] = PointsSymbol[row, 0];
                        TempPointsSymbol[row / 2, 1] = PointsSymbol[row, 1];
                        break;//重新开始新一轮循环。
                    }
                    row += 2;
                    // Temprow++;
                    //合并到只有一个子数组时结束循环
                    if (TempPointsSymbol[0, 1] == Array.Length - 1)
                        break;
                }//判断别进入越界循环(可以进孤单循环)这里指的是PointsSymbol的子数组个数
                while (row <= CopyGroups - 1);
                //
                Copy(Array, TempArray);
                //更新子数组index,row为跳出循环的条件(最后单个子数组或下一个越界的第一个)
                UpdatePointSymbol(PointsSymbol, TempPointsSymbol, row);
                //改变TempPointsSymbol的行数(合并后子数组数)
                mergerows = GNumber(mergerows);
                CopyGroups = GNumberTwo(CopyGroups);
                //合并到只有一个子数组时结束循环
                if (PointsSymbol[0, 1] == Array.Length - 1)
                    break;
            }
            //输出
        }
        public int GNumber(int Value)
        {
            if (Value % 2 == 0)
                Value /= 2;
            else
                Value -= 1;

return Value;
        }
        public int GNumberTwo(int Value)
        {
            if (Value % 2 == 0)
                mergerows = Value / 2;
            else
                mergerows = Value / 2 + 1;
            return mergerows;
        }
        public void MergeThree(int[] Array, int[] Temp, int left, int leftend, int right, int rightend)
        {
            //合并语句
            int index = left;
            while (left <= leftend && right <= rightend)
                Temp[index++] = Array[left] >= Array[right] ? Array[right++] : Array[left++];
            while (left <= leftend)
                Temp[index++] = Array[left++];
            while (right <= rightend)
                Temp[index++] = Array[right++];
        }
        public void MergePointSymbol(int[,] PointsSymbol, int[,] TempPointsSymbol, int row)
        {
            int rowindex = row / 2;
            TempPointsSymbol[rowindex, 0] = PointsSymbol[row, 0];
            TempPointsSymbol[rowindex, 1] = PointsSymbol[row + 1, 1];
        }
        public void UpdatePointSymbol(int[,] PointsSymbol, int[,] TempPointsSymbol, int rows)
        {
            int row = 0;
            //if (mergerows % 2 == 0)
            //{
            for (; row < TempPointsSymbol.GetLength(0); row++)
            {
                for (int col = 0; col < 2; col++)
                    PointsSymbol[row, col] = TempPointsSymbol[row, col];
            }
            //后面的清零
            for (; row < PointsSymbol.GetLength(0); row++)
            {
                for (int col2 = 0; col2 < 2; col2++)
                    PointsSymbol[row, col2] = 0;
            }
            //}
            ////补剩下的index组,
            //else
            //{
            //    for (int row2 = 0; row2 < TempPointsSymbol.GetLength(0); row2++)
            //    {
            //        for (int col3 = 0; col3 < 2; col3++)
            //            PointsSymbol[row2, col3] = TempPointsSymbol[row2, col3];
            //    }
            //    //最后一个子数组的index只有一个。
            //    int row3 = TempPointsSymbol.GetLength(0);
            //    PointsSymbol[row3, 0] = PointsSymbol[rows, 0];
            //    PointsSymbol[row3, 1] = PointsSymbol[rows, 1];
            //    //后面的清零
            //    for (int row4 = row3 + 1; row4 < PointsSymbol.GetLength(0); row4++)
            //    {
            //        for (int col4 = 0; col4 < 2; col4++)
            //            PointsSymbol[row4, col4] = 0;
            //    }
            //}

}
        public int[,] LinearPoints(int[] Array)
        {
            Groups = 1;
            int StartPoint = 0;
            int row = 0;
            int col = 0;
            //最糟糕的情况就是有Array.Length行。
            int[,] PointsSet = new int[Array.Length, 2];
            //线性扫描Array,划分数组
            //初始前index=0
            PointsSet[row, col] = 0;
            do
            {
                //判断升序子数组最终的index开关
                bool Judge = false;
                //从Array第二个数判断是否要结束或者是否是升序子数组.
                while (++StartPoint < Array.Length && Array[StartPoint] < Array[StartPoint - 1])
                {
                    //打开第一个升序子数组结束的index开关
                    Judge = true;
                    //重新开始第二个升序子数组的前index
                    PointsSet[row, col + 1] = StartPoint - 1;
                    //计算子数组个数
                    Groups++;
                    //换行记录自然子数组的index
                    row++;
                    break;
                    //--StartPoint;
                }
                //升序子数组结束index
                if (Judge)
                    PointsSet[row, col] = StartPoint;
                //else
                //    --StartPoint;
            } while (StartPoint < Array.Length);
            //最终index=StartPoint - 1,但是糟糕情况下还有剩余若干行为: 0,0 ...
            PointsSet[row, col + 1] = StartPoint - 1;
            //调用展示方法          
            DisplaySubarray(Array, PointsSet, Groups);
            return PointsSet;
        }
        public void DisplaySubarray(int[] Array, int[,] PointsSet, int Groups)
        {
            Console.WriteLine("Subarray is {0}:", Groups);
            //展示子数组的前后index
            for (int r = 0; r < Groups; r++)
            {
                for (int c = 0; c < PointsSet.GetLength(1); c++)
                {
                    Console.Write(PointsSet[r, c]);
                    if (c < PointsSet.GetLength(1) - 1)
                        Console.Write(",");
                }
                Console.Write("\t\t");
            }
            Console.WriteLine();
            //展示分出的子数组
            for (int v = 0; v < Groups; v++)
            {
                int i = 1;
                for (int r = PointsSet[v, 0]; r <= PointsSet[v, 1]; r++)
                {
                    Console.Write(Array[r] + " ");
                    i++;
                }
                if (i <= 3)
                    Console.Write("\t\t");
                else
                    Console.Write("\t");
                if (PointsSet[v, 1] == Array.Length)
                    break;
            }
        }

public void Copy(int[] Array, int[] merge)
        {
            //一部分排好序的元素替换掉原来Array中的元素
            for (int i = 0; i < Array.Length; i++)
            {
                Array[i] = merge[i];
            }
        }
        //输出
        public override string ToString()
        {
            string temporary = string.Empty;

foreach (var element in Array27)
                temporary += element + " ";

temporary += "\n";
            return temporary;
        }
    }
}

(0)

相关推荐

  • 老生常谈比较排序之归并排序(递归)

    归并排序里运用到算法里很重要的一个思想--分治法:将原问题分解为几个规模较小但类似于原问题的子问题--<算法导论>. 在每一层递归中都有3个步骤: 1.分解问题 2.解决问题 3.合并问题的解 举例待排序数组:{6, 5, 3, 1, 7, 2, 4},将它原始序列做分解. 可以经过不断的递归分解可以看到已经把原始数组序列不断分解为最小单位,接下来不妨将它们看做是二叉树的叶子节点. 将他们进行两两归并排序形成二叉树(也称为2路归并算法),可见二叉树的根节点即为最终序列.在这个过程中我们完成了剩

  • 归并排序的递归实现与非递归实现代码

    归并排序归并排序是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.值得注意的是归并排序是一种稳定的排序方法.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为2-路归并.算法描述归并操作的工作原理如下:第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置第三步:比较两个指针

  • C#递归算法之归并排序

    归并排序是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表,再对半子表排序,最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列,归并排序包括两个步骤,分别为: 1)划分子表 2)合并半子表 首先我们来讨论归并算法,归并算法将一系列数据放到一个向量中,索引范围为[first,last],这个序列由两个排好序的子表构成,以索引终点(mid)为分界线,以下面一个序列为例 7,10,19,25,12,17,21,30,48 这样的一个序列中,分为两个子序列 7,10,19,25  和

  • Java编程获取文件列表及子文件目录的方法(非递归)

    废话不谈,直接进入正题,理解见代码注释. // 非递归 public List<String> scanFiles(String path) { List<String>filePaths = new ArrayList<String>(); LinkedList<File> list = new LinkedList<File>(); File dir = new File(path); File[] file = dir.listFiles(

  • Java实现的二叉树常用操作【前序建树,前中后递归非递归遍历及层序遍历】

    本文实例讲述了Java实现的二叉树常用操作.分享给大家供大家参考,具体如下: import java.util.ArrayDeque; import java.util.Queue; import java.util.Stack; //二叉树的建树,前中后 递归非递归遍历 层序遍历 //Node节点 class Node { int element; Node left; Node right; public Node() { } public Node(int element) { this.

  • C语言数据结构中二分查找递归非递归实现并分析

    C语言数据结构中二分查找递归非递归实现并分析 前言: 二分查找在有序数列的查找过程中算法复杂度低,并且效率很高.因此较为受我们追捧.其实二分查找算法,是一个很经典的算法.但是呢,又容易写错.因为总是考虑不全边界问题. 用非递归简单分析一下,在编写过程中,如果编写的是以下的代码: #include<iostream> #include<assert.h> using namespace std; int binaty_search(int* arr, size_t n, int x)

  • C++ 中二分查找递归非递归实现并分析

    C++ 中二分查找递归非递归实现并分析 二分查找在有序数列的查找过程中算法复杂度低,并且效率很高.因此较为受我们追捧.其实二分查找算法,是一个很经典的算法.但是呢,又容易写错.因为总是考虑不全边界问题. 用非递归简单分析一下,在编写过程中,如果编写的是以下的代码: #include<iostream> #include<assert.h> using namespace std; int binaty_search(int* arr, size_t n, int x) { asse

  • C#归并排序的实现方法(递归,非递归,自然归并)

    //Main: 复制代码 代码如下: using System;using System.Collections.Generic;using System.Linq;using System.Text; namespace Merge{    class Program    {        static void Main(string[] args)        {            while (true)            {                Console.W

  • c语言版本二叉树基本操作示例(先序 递归 非递归)

    复制代码 代码如下: 请按先序遍历输入二叉树元素(每个结点一个字符,空结点为'='):ABD==E==CF==G== 先序递归遍历:A B D E C F G中序递归遍历:D B E A F C G后序递归遍历:D E B F G C A层序递归遍历:ABCDEFG先序非递归遍历:A B D E C F G中序非递归遍历:D B E A F C G后序非递归遍历:D E B F G C A深度:请按任意键继续. . . 复制代码 代码如下: #include<stdio.h>#include&

  • c#斐波那契数列(Fibonacci)(递归,非递归)实现代码

    //Main 复制代码 代码如下: using System;using System.Collections.Generic;using System.Linq;using System.Text; namespace Fibonacci{    class Program    {        static void Main(string[] args)        {            Console.WriteLine("Would you like to know which

  • C# 实现阶乘 (递归,非递归) 实现代码

    //Main: 复制代码 代码如下: using System;using System.Collections.Generic;using System.Linq;using System.Text; namespace Factorial{    class Program    {        static void Main(string[] args)        {            Function obj = new Function();            Cons

  • Java编程二项分布的递归和非递归实现代码实例

    本文研究的主要内容是Java编程二项分布的递归和非递归实现,具体如下. 问题来源: 算法第四版 第1.1节 习题27:return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p); 计算递归调用次数,这里的递归式是怎么来的? 二项分布: 定义:n个独立的是/非试验中成功次数k的离散概率分布,每次实验成功的概率为p,记作B(n,p,k). 概率公式:P(ξ=K)= C(n,k) * p^k * (1-p)^(n-k

  • C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    本文实例讲述了C语言二叉树常见操作.分享给大家供大家参考,具体如下: 一.基本概念 每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒. 性质: 1.非空二叉树的第n层上至多有2^(n-1)个元素. 2.深度为h的二叉树至多有2^h-1个结点. 满二叉树:所有终端都在同一层次,且非终端结点的度数为2. 在满二叉树中若其深度为h,则其所包含的结点数必为2^h-1. 完全二叉树:除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐,即集中在左面的位置上,不能有空位置. 对于完全二叉

随机推荐