《算法之美》---归并排序

将一个大序列的排序问题分解为对两个或多个子序列的排序问题，然后对子序列递归使用同样的方式进行排序；在子序列排好序后，将结果合并起来即可。利用这种思想的排序方法就是著名的归并排序。之所以称为归并排序，是因为整个算法的成本由归并部分决定。

归并算法描述如下：

1）如果n=1，排序完成；

2）将序列分解为两个子序列A[1 … ceiling(n/2)]和A[ceiling(n/2)+1 … n]；

3）递归对子序列A[1 … ceiling(n/2)]和A[ceiling(n/2)+1 … n]进行排序；

4）将排好序的两个子序列进行归并。

归并排序使用的是分治策略，而分治策略的关键是分解和合并。归并排序的分解很简单：直接将序列从中间斩断；但合并的时候需要将两个排好序的子序列按次序进行合适的穿插，从而获得原序列的一个排序。

合并时我们使用两个指针：一个指向A序列里下一个要归并的元素，一个指向B序列里下一个要归并的元素。每步我们对这两个指针所指的元素进行比较，小者被归并到C序列里，并将指向较小者的指针往后推进一个元素，另一个指针保持不动。这样循环往复直到一个子序列为空。这时，另一个子序列中剩下的所有元素直接复制到C序列末尾即可。

注意：归并排序在最坏、平均和最好情况下时间复杂度都是Θ(nlogn)。这是归并排序一个显著的特点：一视同仁。

/*

函数名： MergeSort

功能： 归并排序

模板参数说明：T必须支持小于操作

参数说明： data待排序数组, size待排序数组大小

前置条件： data!=NULL, size>0

后置条件： data按非降序排列

用法：

#include <algorithm>

int arr[]={10,9,8,4,5,7,6,3,1,4};

MergeSort(arr, 10);

*/

template <typename T>

void MergeSort (T data[], int size)

{

if ( size>1 )

{

//预处理

int mid=size/2;

int numOfleft=mid;

int numOfright=size-mid;

T* left=new T[numOfleft];

T* right=new T[numOfright];

//分解

std::copy(data, data+numOfleft, left);

std::copy(data+numOfleft, data+size, right);

MergeSort(left, numOfleft);

MergeSort(right, numOfright);

//合并

std::merge(left, left+numOfleft, right, right+numOfright, data);

//清理

delete[] left;

delete[] right;

}

}

/*

函数名： MergeSort

功能： 归并排序

模板参数说明：T元素类型, Func函数对象或指针

参数说明： data待排序数组, size待排序数组大小,f函数对象或指针

前置条件： data!=NULL, size>0

后置条件： data按f排列

用法：

#include <algorithm>

bool cmp(int a, int b)

{ return a<b; }

int arr[]={10,9,8,4,5,7,6,3,1,4};

MergeSort(arr, 10，cmp);

*/

template <typename T, typename Func>

void MergeSort (T data[], int size, Func f)

{

if ( size>1 )

{

int mid=size/2;

int numOfleft=mid;

int numOfright=size-mid;

T* left=new T[numOfleft];

T* right=new T[numOfright];

std::copy(data, data+numOfleft, left);

std::copy(data+numOfleft, data+size, right);

MergeSort(left, numOfleft, f);

MergeSort(right, numOfright, f);

std::merge(left, left+numOfleft, right, right+numOfright, data, f);

delete[] left;

delete[] right;

}

}