排序——4.归并排序

归并排序   开始之前，看这样一个例子：假设桌子上有两堆扑克牌，每堆只有一张，我们比较这两张扑克牌，将小的那个放到一个新堆里，再把大的那个放到小的那个上边。其实这 样就完成了一次简单的归并排序。   先通过上边的例子了解下什么是归并排序，再往下看就容易理解了。   刚刚的例子里将要合并的两个部分都只有一个元素，下面是对于多个多元素的合并：   假设我们已经有了两个早已经排序好了的数组，分别是a[N],b[M]。数组a中的元素从下标0到下标N-1逐渐增大（a[0]最小，a[N-1]最大），数组b也是这样。 1.我们先将a[0]和b[0]比较，先把小的那个放到一个新数组c中（c[0]=a[0]，假设a[0]<b[0]）然后再把a[0]和b[0]中较大的那个放到新数组c中（c[1]=b[0]）。 2.再比较a[1]和b[1]，，先把小的那个放到一个新数组c中（c[2]=a[1],假设a[1]<b[1]）然后再把a[0]和b[0]中较大的那个放到新数组c中（c[3]=b[1]）。 3.以此类推直到所有元素都放到c中。这样就将两个已经排好序的数组合并到一起了，并且也排好序了。 有了上边这个方法，我们就可以实现归并排序了。归并排序总结为一句话就是： 先分解，再合并。每次对数组一分为二，将分解开的部分再对半分，直到分解到每部分都只剩一个元素，然后再按照开始的那个例子逆着合并回去。 正式开始： 分解 假设有数组a[10]={8,4,6,3,2,1,8,5,11,25}。 先将它一分为二，拆解成这样： 再把得到的这两部分，分别一分为二从，拆解成这样： 一直这样分下去，直到每个部分只有一个元素： （颜色差点不够用的···） 下图这样更直观一些（分解过程）： 等到分解到每个部分都只有一个元素了，就要开始合并了，回想最开始的那个例子，逆着合并回去。 直接看图吧：

代码：

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace 归并排序 { class Program { static void Main(string[] args) { int[] a = new int[] { 8, 4, 6, 3, 2, 1, 8, 5, 11, 25 }; Console.WriteLine("未排序之前的顺序："); foreach (int s in a) { Console.WriteLine(" {0}", s); } int[] b = new int[10]; MergeSort(a, b, 0, a.Length-1 ); Console.WriteLine("排序之后的顺序："); foreach (int s in a) { Console.WriteLine(" {0}", s); } Console.ReadKey(); } public static void MergeSort(int[] sourceArr, int[] tempArr, int startIndex, int endIndex) { int midIndex; if (startIndex < endIndex) { midIndex = (startIndex + endIndex) / 2; MergeSort(sourceArr, tempArr, startIndex, midIndex); MergeSort(sourceArr, tempArr, midIndex + 1, endIndex); Merge(sourceArr, tempArr, startIndex, midIndex, endIndex); } } public static void Merge(int[] sourceArr, int[] tempArr, int startIndex, int midIndex, int endIndex) { int L = startIndex, R = midIndex + 1, k = startIndex; while (L != midIndex + 1 && R != endIndex + 1) { if (sourceArr[L] >= sourceArr[R]) tempArr[k++] = sourceArr[R++]; else tempArr[k++] = sourceArr[L++]; } while (L != midIndex + 1)//某一方已经结束，合并另一方剩下所有 tempArr[k++] = sourceArr[L++]; while (R != endIndex + 1)//某一方已经结束，合并另一方剩下所有 tempArr[k++] = sourceArr[R++]; for (int i = startIndex; i <= endIndex; i++) sourceArr[i] = tempArr[i]; } } }

就算明白了归并排序的原理，转化成代码的过程也没有想象中那么简单，做了一个小视频来演示以上代码在合并的时候是如何工作的，该视频还有一些瑕疵，并不能完全代表实际工作过程，仅用作参考。

http://v.youku.com/v_show/id_XMTQ4NDc5NTUzNg==.html