归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

从上往下的归并排序过程

1. 分解 -- 将当前区间一分为二，即求分裂点 mid = (low + high)/2;
2. 求解 -- 递归地对两个子区间a[low...mid] 和 a[mid+1...high]进行归并排序。递归的终结条件是子区间长度为1。
3. 合并 -- 将已排序的两个子区间a[low...mid]和 a[mid+1...high]归并为一个有序的区间a[low...high]。

C语言的实现：

MergingSort.h

#include <stdio.h>
#include <cstdlib>
#define MAXSIZE 100
typedef int Elemtype;
void MSort(int SR[], int Temp[], int l, int r);
void Merge(int SR[], int Temp[], int l, int r, int rightEnd);
void MergeSort(int SR[], int length);

//Temp临时数组
void MSort(int SR[], int Temp[], int l, int r)
{
    int mid;
    if (l < r) //只剩一个元素，不需要再分
    {
        mid = (l + r) / 2;
        MSort(SR, Temp, l, mid);
        MSort(SR, Temp, mid + 1, r);
        //归并
        Merge(SR, Temp, l, mid + 1, r);
    }
}

//SR-待排数组,Temp-临时数组,l-左边数组起始位置,r-右边数组起始位置,rightEnd-右边数组终止位置
void Merge(int SR[], int Temp[], int l, int r, int rightEnd)
{
    int leftEnd, ElementNum, Tmp;
    leftEnd = r - 1;               //左边数组终点位置
    Tmp = l;                       //归并后数组的起始位置
    ElementNum = rightEnd - l + 1; //元素个数

    //归并过程
    while (l <= leftEnd && r <= rightEnd)
    {
        if (SR[l] <= SR[r])
            Temp[Tmp++] = SR[l++];
        else
            Temp[Tmp++] = SR[r++];
    }
    //剩余
    while (l <= leftEnd)
        Temp[Tmp++] = SR[l++];
    while (r <= rightEnd)
        Temp[Tmp++] = SR[r++];
    //将临时数组Temp中的元素赋值给SR
    for (int i = 0; i < ElementNum; i++, rightEnd--)
        SR[rightEnd] = Temp[rightEnd];
}
//为归并函数设置统一接口
void MergeSort(int SR[], int length)
{
    int *Temp;
    Temp = (int *)malloc(length * sizeof(int));

    if (Temp)
    {
        MSort(SR, Temp, 0, length - 1);
        free(Temp);
    }
    else
        printf("error!\n");
}

MergingSort_test.c

#include "MergingSort.h"

int main()
{
    int length, i;
    printf("Enter nums:\n");
    scanf("%d", &length);
    int *SR;
    SR = (int *)malloc(length*sizeof(int));
    printf("Enter SR[]:\n");
    for (i = 0; i < length; i++)
        scanf("%d", &SR[i]);
    MergeSort(SR, length);
    for (i = 0; i < length; i++)
        printf("%d ", SR[i]);
    printf("\n");

    system("PAUSE");
    return 0;
}