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>
/// 归并排序(递归）
/// 核心思想：（分治）
/// 将待排序元素（递归直至元素个数为１）分成左右两个大小大致相同的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;
}
}
}