//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] = ran.Next(1, 100);
}
//选择
public void ToMergeSort()
{
MergeSort(Array27);
}
public void ToRecursiveMergeSort()
{
RecursiveMergeSort(Array27, 0, Array27.Length - 1);
}
public void ToNaturalMergeSort()
{
NaturalMergeSort(Array27);
}

/// <summary>
/// 归并排序(递归）
/// 核心思想：（分治）
/// 将待排序元素（递归直至元素个数为１）分成左右两个大小大致相同的2个子集合，然后，
/// 分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合．
/// 核心算法时间复杂度：
/// T(n)=O(nlogn)
/// 参考 优秀代码: http://zh.wikipedia.org/wiki/%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F
/// http:///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;
}
}
}