手机
当前位置:查字典教程网 >编程开发 >C#教程 >C#归并排序的实现方法(递归,非递归,自然归并)
C#归并排序的实现方法(递归,非递归,自然归并)
摘要://Main:复制代码代码如下:usingSystem;usingSystem.Collections.Generic;usingSyste...

//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("tt");

}

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("tt");

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;

}

}

}

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

【C#归并排序的实现方法(递归,非递归,自然归并)】相关文章:

两路归并的数组与链表的实现方法

解决用Aspose.Words,在word文档中创建表格的实现方法

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

C# String Replace高效的实例方法

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

C#最简单的关闭子窗体更新父窗体的实现方法

C# 将字节流转换为图片的实例方法

c#启动EXE文件的方法实例

C# char类型字符转换大小写的实现代码

C#实现图片分割方法与代码

精品推荐
分类导航