算法 - 归并排序（C#）

/* * 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 */