归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
从上往下的归并排序过程
从上往下的归并排序：它与"从下往上"在排序上是反方向的。它基本包括3步：
- 分解 -- 将当前区间一分为二，即求分裂点 mid = (low + high)/2;
- 求解 -- 递归地对两个子区间a[low...mid] 和 a[mid+1...high]进行归并排序。递归的终结条件是子区间长度为1。
- 合并 -- 将已排序的两个子区间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;
}
