算法 - 歸并排序（C#）
來源：程序員人生 發布時間：2014-12-16 08:53:17 閱讀次數：3046次
/*
* MergeSorter.cs - by Chimomo
*
* 歸并排序是建立在歸并操作上的排序算法，該算法是分而治之策略（Divide and Conquer）的1個非常典型的利用。
*
* 歸并操作的基本原理：
* 1、申請空間，使其大小為兩個已排序序列之和，該空間用來寄存歸并后的序列。
* 2、設置兩個指針，最初位置分別為兩個已排序序列的起始位置。
* 3、比較兩個指針所指向的元素，選擇相對小的元素放入歸并序列，并移動指針到下1位置。
* 4、重復步驟3直到某1指針超越序列尾部。
* 5、將另外一序列剩下的所有元素直接復制到歸并序列尾部。
*
* 歸并排序的基本原理（假定序列共有n個元素）：
* 1、將序列每相鄰兩個數字進行歸并操作（Merge），構成Floor(n/2)個序列，排序后每一個序列包括兩個無素。
* 2、將上述序列再次歸并，構成Floor(n/4)個序列，每一個序列包括4個元素。
* 3、重復步驟2，直到所有元素排序終了。
*
* 歸并排序速度僅次于快速排序，是1種穩定的排序算法，1般用于對整體無序，但是各子項相對有序的序列。
*/
using System;
namespace Sort
{
public static class MergeSorter
{
/// <summary>
/// 2路歸并：將兩個有序序列歸并成1個有序序列。
/// </summary>
/// <param name="a">待歸并序列</param>
/// <param name="s1">第1個有序序列的起始下標</param>
/// <param name="s2">第2個有序序列的起始下標</param>
/// <param name="e2">第2個有序序列的結束下標</param>
private static void Merge(int[] a, int s1, int s2, int e2)
{
int[] tmp = new int[e2 - s1 + 1];
int i = s1, j = s2, k = 0;
while (i < s2 && j <= e2)
{
if (a[i] <= a[j])
{
tmp[k] = a[i];
k++;
i++;
}
else
{
tmp[k] = a[j];
j++;
k++;
}
}
while (i < s2)
{
tmp[k] = a[i];
i++;
k++;
}
while (j <= e2)
{
tmp[k] = a[j];
j++;
k++;
}
Array.Copy(tmp, 0, a, s1, tmp.Length);
}
/// <summary>
/// 歸并排序算法。
/// </summary>
/// <param name="a">待排序序列</param>
/// <param name="s">待排序序列的起始下標</param>
/// <param name="length">每次要歸并的有序集合的長度</param>
public static void MergeSort(int[] a, int s, int length)
{
int size = a.Length;
int mid = size / (length << 1);
int c = size & ((length << 1) - 1);
// 歸并到只剩1個有序序列的時候結束算法。
if (mid == 0)
{
return;
}
// 進行1趟歸并排序。
for (int i = 0; i < mid; ++i)
{
s = i * 2 * length;
Merge(a, s, s + length, (length << 1) + s - 1);
}
// 將剩下的元素和倒數1個有序集合歸并。
if (c != 0)
{
Merge(a, size - c - 2 * length, size - c, size - 1);
}
// 遞歸履行下1趟歸并排序。
MergeSort(a, 0, 2 * length);
}
}
}
/*
* Program.cs - by Chimomo
*/
using System;
namespace Sort
{
static class Program
{
static void Main()
{
int[] a = { 4, 3, 6, 1, 2, 5, 34, 7, ⑴, 340, ⑵34, ⑼, 909 };
MergeSorter.MergeSort(a, 0, 1);
foreach (var i in a)
{
Console.Write(i + " ");
}
Console.WriteLine();
}
}
}
/*
Output:
⑵34 ⑼ ⑴ 1 2 3 4 5 6 7 34 340 909
*/
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
