C#歸并排序的實(shí)現(xiàn)方法(遞歸,非遞歸,自然歸并)
//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("請(qǐng)選擇：");
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】//抱歉，實(shí)在不知怎么學(xué)習(xí)英語，語法什么錯(cuò)誤之處還請(qǐng)見諒。
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>
/// 歸并排序(遞歸）
/// 核心思想：（分治）
/// 將待排序元素（遞歸直至元素個(gè)數(shù)為１）分成左右兩個(gè)大小大致相同的2個(gè)子集合，然后，
/// 分別對(duì)2個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合．
/// 核心算法時(shí)間復(fù)雜度：
/// T(n)=O(nlogn)
/// 參考 優(yōu)秀代碼: 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)
{
//對(duì)前半部分遞歸拆分
RecursiveMergeSort(Array, left, middle);
//對(duì)后半部分遞歸拆分
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;
//動(dòng)態(tài)臨時(shí)二維數(shù)組存放分割為兩個(gè)小Array的數(shù)組排列順序后的數(shù)據(jù)
int[] merge = new int[right + 1];
int index = 0;
//對(duì)兩個(gè)小數(shù)組合并排序
while (leftindex <= middle && rightindex <= right)
merge[index++] = (Array[leftindex] - Array[rightindex]) >= 0 ? Array[rightindex++] : Array[leftindex++];
//有一側(cè)子數(shù)列遍歷完后，將另外一側(cè)子數(shù)列剩下的數(shù)依次放入暫存數(shù)組中（有序）
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];
}
//將有序的數(shù)列 寫入目標(biāo)數(shù)組 ，即原來把Array數(shù)組分為兩個(gè)小Array數(shù)組后重新有序組合起來(覆蓋原數(shù)組）
index = 0;
for (int i = left; i <= right; i++)
Array[i] = merge[index++];
}
/// <summary>
/// 歸并排序(非遞歸）
/// 核心思想：（分治）
/// 對(duì)n個(gè)數(shù)的數(shù)列每相鄰兩個(gè)元素排序，組成n/2個(gè)或（n+1)/2個(gè)子數(shù)組，單個(gè)的不比了直接進(jìn)入下一輪。
/// 然后對(duì)每個(gè)相鄰的子數(shù)組再排序，以此類推最后得到排好序的數(shù)列
/// forexample： 59 35 54 28 52
/// 排序And分： 35 59. 28 54. 52
/// 排序And分： 28 35 54 59. 52
/// 結(jié)果： 28 35 52 54 59
/// 核心算法時(shí)間復(fù)雜度：
/// T(n)=O(nlogn)
/// </summary>
/// <param name="Array"></param>
public void MergeSort(int[] Array)
{
//index固定的數(shù)組
int[] merge = new int[Array.Length];
int P = 0;
while (true)
{
int index = 0;
//子數(shù)組元素的個(gè)數(shù)
int ENumb = (int)Math.Pow(2, P);
//一個(gè)子數(shù)組中的元素個(gè)數(shù)與數(shù)組的一半元素個(gè)數(shù)比較大小
//最糟糕的情況最右邊的數(shù)組只有一個(gè)元素
if (ENumb < Array.Length)
{
while (true)
{
int TorFAndrightindex = index;
//最后一個(gè)子數(shù)組的第一個(gè)元素的index與數(shù)組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)
{
//換分兩個(gè)子數(shù)組的index(千萬不能用middle = (right + left) / 2劃分）
// 1
int left = index;
int middle = left + ENumb - 1;
//（奇數(shù)時(shí)）
//排除middleindex越界
if (middle >= Array.Length)
{
middle = index;
}
//同步化merge數(shù)組的index
int mergeindex = index;
// 2
int right;
int middleTwo = (index + ENumb - 1) + 1;
right = index + ENumb + ENumb - 1;
//排除最后一個(gè)子數(shù)組的index越界.
if (right >= Array.Length - 1)
{
right = Array.Length - 1;
}
//排序兩個(gè)子數(shù)組并復(fù)制到merge數(shù)組
while (left <= middle && middleTwo <= right)
{
merge[mergeindex++] = Array[left] >= Array[middleTwo] ? Array[middleTwo++] : Array[left++];
}
//兩個(gè)子數(shù)組中其中一個(gè)比較完了（Array[middleTwo++] 或Array[left++]），
//把其中一個(gè)數(shù)組中剩下的元素復(fù)制進(jìn)merge數(shù)組。
if (left <= middle)
{
//排除空元素.
while (left <= middle && mergeindex < merge.Length)
merge[mergeindex++] = Array[left++];
}
if (middleTwo <= right)
{
while (middleTwo <= right)
merge[mergeindex++] = Array[middleTwo++];
}
//判斷是否合并至最后一個(gè)子數(shù)組了
if (right + 1 >= Array.Length)
Copy(Array, merge);
}
/// <summary>
/// 自然歸并排序:
/// 對(duì)于初始給定的數(shù)組,通常存在多個(gè)長(zhǎng)度大于1的已自然排好序的子數(shù)組段.
/// 例如,若數(shù)組a中元素為{4,8,3,7,1,5,6,2},則自然排好序的子數(shù)組段
/// 有{4,8},{3,7},{1,5,6},{2}.
/// 用一次對(duì)數(shù)組a的線性掃描就足以找出所有這些排好序的子數(shù)組段.
/// 然后將相鄰的排好序的子數(shù)組段兩兩合并,
/// 構(gòu)成更大的排好序的子數(shù)組段({3,4,7,8},{1,2,5,6}).
/// 繼續(xù)合并相鄰排好序的子數(shù)組段,直至整個(gè)數(shù)組已排好序.
/// 核心算法時(shí)間復(fù)雜度：
/// T(n)=○(n);
/// </summary>
public void NaturalMergeSort(int[] Array)
{
//得到自然劃分后的數(shù)組的index組（每行為一個(gè)自然子數(shù)組）
int[,] PointsSymbol = LinearPoints(Array);
//子數(shù)組只有一個(gè)。
if (PointsSymbol[0, 1] == Array.Length - 1)
return;
//多個(gè)(至少兩個(gè)子數(shù)組）...
else
//可以堆棧調(diào)用嗎？
NaturalMerge(Array, PointsSymbol);
}
public void NaturalMerge(int[] Array, int[,] PointsSymbol)
{
int left;
int right;
int leftend;
int rightend;
mergerows = GNumberTwo(Groups);
CopyGroups = Groups;
//固定狀態(tài)
int[] TempArray = new int[Array.Length];
//循環(huán)取每個(gè)自然子數(shù)組的index
while (true)
{
// int Temprow = 1;
//只記錄合并后的子數(shù)組(”《應(yīng)該為》“動(dòng)態(tài)的）
int[,] TempPointsSymbol = new int[mergerows, 2];
int row = 0;
do
{
//最重要的判斷：最后(一組子數(shù)組)是否可配對(duì)
if (row != CopyGroups - 1)
{ //以上條件也可以含有(& 和&&的區(qū)別)短路運(yùn)算
//參考: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
{
////默認(rèn)剩下的單獨(dú)一個(gè)子數(shù)組已經(jīng)虛擬合并。然后Copy進(jìn)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;//重新開始新一輪循環(huán)。
}
row += 2;
// Temprow++;
//合并到只有一個(gè)子數(shù)組時(shí)結(jié)束循環(huán)
if (TempPointsSymbol[0, 1] == Array.Length - 1)
break;
}//判斷別進(jìn)入越界循環(huán)(可以進(jìn)孤單循環(huán)）這里指的是PointsSymbol的子數(shù)組個(gè)數(shù)
while (row <= CopyGroups - 1);
//
Copy(Array, TempArray);
//更新子數(shù)組index，row為跳出循環(huán)的條件（最后單個(gè)子數(shù)組或下一個(gè)越界的第一個(gè)）
UpdatePointSymbol(PointsSymbol, TempPointsSymbol, row);
//改變TempPointsSymbol的行數(shù)（合并后子數(shù)組數(shù)）
mergerows = GNumber(mergerows);
CopyGroups = GNumberTwo(CopyGroups);
//合并到只有一個(gè)子數(shù)組時(shí)結(jié)束循環(huán)
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;
}
//}
////補(bǔ)剩下的index組，
//else
//{
// for (int row2 = 0; row2 < TempPointsSymbol.GetLength(0); row2++)
// {
// for (int col3 = 0; col3 < 2; col3++)
// PointsSymbol[row2, col3] = TempPointsSymbol[row2, col3];
// }
// //最后一個(gè)子數(shù)組的index只有一個(gè)。
// 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，劃分?jǐn)?shù)組
//初始前index=0
PointsSet[row, col] = 0;
do
{
//判斷升序子數(shù)組最終的index開關(guān)
bool Judge = false;
//從Array第二個(gè)數(shù)判斷是否要結(jié)束或者是否是升序子數(shù)組.
while (++StartPoint < Array.Length && Array[StartPoint] < Array[StartPoint - 1])
{
//打開第一個(gè)升序子數(shù)組結(jié)束的index開關(guān)
Judge = true;
//重新開始第二個(gè)升序子數(shù)組的前index
PointsSet[row, col + 1] = StartPoint - 1;
//計(jì)算子數(shù)組個(gè)數(shù)
Groups++;
//換行記錄自然子數(shù)組的index
row++;
break;
//--StartPoint;
}
//升序子數(shù)組結(jié)束index
if (Judge)
PointsSet[row, col] = StartPoint;
//else
// --StartPoint;
} while (StartPoint < Array.Length);
//最終index=StartPoint - 1，但是糟糕情況下還有剩余若干行為： 0,0 ...
PointsSet[row, col + 1] = StartPoint - 1;
//調(diào)用展示方法
DisplaySubarray(Array, PointsSet, Groups);
return PointsSet;
}
public void DisplaySubarray(int[] Array, int[,] PointsSet, int Groups)
{
Console.WriteLine("Subarray is {0}:", Groups);
//展示子數(shù)組的前后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();
//展示分出的子數(shù)組
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;
}
}
}
相關(guān)文章
C#實(shí)現(xiàn)基于IE內(nèi)核的簡(jiǎn)單瀏覽器完整實(shí)例
這篇文章主要介紹了C#實(shí)現(xiàn)基于IE內(nèi)核的簡(jiǎn)單瀏覽器,較為詳細(xì)的分析了C#實(shí)現(xiàn)瀏覽器的原理與主要功能實(shí)現(xiàn)方法,并附帶完整實(shí)例供大家下載,需要的朋友可以參考下2015-07-07
如果我們著重處理一個(gè)以位為單位的數(shù)據(jù)時(shí)，就可以考慮使用位數(shù)組。本文就介紹了C# 位圖BitArray的使用，感興趣的可以了解一下2021-06-06
C# BeginInvoke實(shí)現(xiàn)異步編程方式
這篇文章主要介紹了C# BeginInvoke實(shí)現(xiàn)異步編程方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-01-01
c#異步讀取數(shù)據(jù)庫(kù)與異步更新ui的代碼實(shí)現(xiàn)
這篇文章主要介紹了c#從數(shù)據(jù)庫(kù)里取得數(shù)據(jù)并異步更新ui的方法，大家參考使用吧2013-12-12
C#實(shí)現(xiàn)獲取文件大小并進(jìn)行比較
這篇文章主要為大家詳細(xì)介紹了C#如何實(shí)現(xiàn)獲取文件大小進(jìn)行單位轉(zhuǎn)換與文件大小比較功能，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下2023-03-03
下面小編就為大家?guī)硪黄獪\談C#中的Infinity和NaN。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-07-07
C#精確到納秒級(jí)別的計(jì)時(shí)器類實(shí)現(xiàn)代碼
這篇文章主要介紹了C#精確到納秒級(jí)別的計(jì)時(shí)器類,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-08-08
C# TextBox 擴(kuò)展方法數(shù)據(jù)驗(yàn)證詳細(xì)說明
C# TextBox 擴(kuò)展方法數(shù)據(jù)驗(yàn)證詳細(xì)說明，需要的朋友可以參考一下2013-03-03
C#利用性能計(jì)數(shù)器監(jiān)控網(wǎng)絡(luò)狀態(tài)
這篇文章主要為大家詳細(xì)介紹了C#利用性能計(jì)數(shù)器監(jiān)控網(wǎng)絡(luò)狀態(tài)的相關(guān)資料，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-01-01
C# AE之返回上一級(jí)和下一級(jí)的實(shí)戰(zhàn)操作
這篇文章主要介紹了C# AE之返回上一級(jí)和下一級(jí)的實(shí)戰(zhàn)操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2021-01-01