排序——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