数据结构和算法系列8 七大排序之归并排序

这一篇要总结的是归并排序算法，这也是七大排序的最后一种排序算法。

首先来看一下归并排序(Merge Sort)的基本原理。它的原理是假设初始序列有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两合并，得到n/2个长度为2或1的有序子序列；再两两归并，… … ，如此重复，直至得到一个长度为n的有序序列为止，这两排序方法就称为归并排序。

下面以一张图来说明归并排序的数据交换过程：

C#版实现代码：

namespace MergeSort.CSharp
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] array = { 50,10,90,30,70,40,80,60,20 };

            Console.WriteLine("********************归并排序********************");
            Console.WriteLine("排序前：");
            Display(array);

            MergeSort(array, new int[array.Length], 0, array.Length - 1);
            Console.WriteLine("排序后：");
            Display(array);

            Console.ReadKey();
        }

        /// <summary>
        /// 归并排序算法
        /// </summary>
        /// <param name="array">待排序的数组</param>
        /// <param name="temparray">临时数组</param>
        /// <param name="head">列表开始位置</param>
        /// <param name="rear">列表结束位置</param>
        public static void MergeSort(int[] array, int[] temparray, int head, int rear)
        {
            if (head < rear)
            {
                //取分割位置
                int middle = (head + rear) / 2;

                //递归划分数组左序列
                MergeSort(array, temparray, head, middle);

                //递归划分数组右序列
                MergeSort(array, temparray, middle + 1, rear);

                //数组合并操作
                Merge(array, temparray, head, middle + 1, rear);
            }
        }

        /// <summary>
        /// 合并操作(列表的两两合并)
        /// </summary>
        /// <param name="array"></param>
        /// <param name="temparray"></param>
        /// <param name="head"></param>
        /// <param name="middle"></param>
        /// <param name="rear"></param>
        public static void Merge(int[] array, int[] temparray, int head, int middle, int rear)
        {
            //左指针尾
            int headEnd = middle - 1;

            //右指针头
            int rearStart = middle;

            //临时数组的下标
            int tempIndex = head;

            //数组合并后的length长度
            int tempLength = rear - head + 1;

            //先循环两个区间段都没有结束的情况
            while ((headEnd>=head) && (rearStart <= rear))
            {
                //如果发现有序列大，则将此数放入临时数组
                if (array[head] < array[rearStart])
                    temparray[tempIndex++] = array[head++];
                else
                    temparray[tempIndex++] = array[rearStart++];
            }

            //判断左序列是否结束
            while (head <= headEnd)
                temparray[tempIndex++] = array[head++];

            //判断右序列是否结束
            while (rearStart <= rear)
                temparray[tempIndex++] = array[rearStart++];

            //交换数据
            for (int i = 0; i < tempLength; i++)
            {
                array[rear] = temparray[rear];
                rear--;
            }
        }

        private static void Display(IList<int> list)
        {
            Console.WriteLine("
**********展示结果**********
");

            if (list != null && list.Count > 0)
            {
                foreach (var item in list)
                {
                    Console.Write("{0} ", item);
                }
            }
            Console.WriteLine("
**********展示完毕**********
");
        }
    }
}

程序输出结果为：

 

C语言版：

/*包含头文件*/
#include "stdio.h"
#include "stdlib.h"   
#include "io.h"
#include "math.h" 
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100

typedef int Status; 
typedef struct
{
    int data[MAXSIZE];
    int length;    
}SeqList;

/* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] */
void Merge(int SR[],int TR[],int i,int m,int n)
{
    int j,k,l;
    for(j=m+1,k=i;i<=m && j<=n;k++)    /* 将SR中记录由小到大地并入TR */
    {
        if (SR[i]<SR[j])
            TR[k]=SR[i++];
        else
            TR[k]=SR[j++];
    }
    if(i<=m)
    {
        for(l=0;l<=m-i;l++)
            TR[k+l]=SR[i+l];        /* 将剩余的SR[i..m]复制到TR */
    }
    if(j<=n)
    {
        for(l=0;l<=n-j;l++)
            TR[k+l]=SR[j+l];        /* 将剩余的SR[j..n]复制到TR */
    }
}

/*归并排序算法*/
void MSort(int SR[],int TR1[],int s, int t)
{
    int m;
    int TR2[MAXSIZE+1];
    if(s==t)
        TR1[s]=SR[s];
    else
    {
        m=(s+t)/2;                /* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */
        MSort(SR,TR2,s,m);        /* 递归地将SR[s..m]归并为有序的TR2[s..m] */
        MSort(SR,TR2,m+1,t);    /* 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] */
        Merge(TR2,TR1,s,m,t);    /* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] */
    }
}

/* 对顺序表L作归并排序 */
void MergeSort(SeqList *seqList)
{ 
    MSort(seqList->data,seqList->data,0,seqList->length-1);
}


/*打印结果*/
void Display(SeqList *seqList)
{
    int i;
    printf("
**********展示结果**********
");

    for (i=0;i<seqList->length;i++)
    {
        printf("%d ",seqList->data[i]);
    }

    printf("
**********展示完毕**********
");
}

#define N 9
void main()
{
    int i,j;
    SeqList seqList;

    //定义数组和初始化SeqList
    int d[N]={50,10,90,30,70,40,80,60,20};

    for (i=0;i<N;i++)
    {
        seqList.data[i]=d[i];
    }
    seqList.length=N;

    printf("***************归并排序***************
");
    printf("排序前：");
    Display(&seqList);

    MergeSort(&seqList);
    printf("
排序后：");
    Display(&seqList);

    getchar();
}

输出结果同上。