1、归并排序(merge sort)
(1)描述
归并排序采用分治法，先使每个子序列有序，再合并子序列使整体有序。
(2)实现
把数据分成2个部分，直到每部分长度为1，开始进行合并操作：
申请足够大的空间，用来存放2组数据合并之后的数据，
从两组数据的下标[0]开始比较，取较小的数据放到合并空间中，该数组的下标自增1，重复操作直到把两组数据合并到合并空间。
把合并空间的有序数据复制回原数组。
void merge(int data[], int left, int right)
{
int n = (right - left + 1);
int *p = (int * )malloc(n * (sizeof(int)));
int middle = (left + right) / 2;
int k = middle + 1;
int j = left;
int i = 0;
while (j <= middle && k <= right)
{
if (data[k] < data[j])
{
p[i++] = data[k++];
}
else
{
p[i++] = data[j++];
}
}
while (j <= middle)
p[i++] = data[j++];
while (k <= right)
p[i++] = data[k++];
for (i = 0, j = left; j <= right;)
{
data[j++] = p[i++];
}
free(p);
}
void mergesort1(int data[], int left, int right)
{
if (left < right)
{
int middle = (left + right) / 2;
mergesort1(data, left, middle);
mergesort1(data, middle+1, right);
merge(data, left, right);
}
}
可以考虑把malloc的过程放在外面,一开始malloc一个等于原始数据的大空间,节省频繁调用malloc和free的开销.
上面是自顶向下(递归)的实现；
下面是自底向上(循环)的实现：
void mergesort2(int data[], int left, int right)
{
if (left < right)
{
int gap = 2; // 2 ~ n
int left2, right2;
int n = (right - left + 1);
while(gap <= n)
{
left2 = left;
right2 = left + gap-1;
while(right2 <= right)
{
merge(data, left2, right2);
if (right2 != right && right - right2 < gap) // 防漏
right2 = right;
else
{
left2 += gap;
right2 += gap;
}
}
gap *= 2;
}
}
}
(3) 时间复杂度
把数据分为 2 个部分，需要 log2n 次分完，
然后再对 2 个部分分别进行递归排序，所以一共是 2*log2n 次归并，复杂度是 O(logn) ；
把 2 个数组合并为 1 个，再复制回原来的数组，复杂度是 O(n) ，
所以总的时间复杂度是 O(nlogn) 。
(4)空间复杂度 O(n)
(5)稳定性：稳定
2、多路归并
假设有k个数组，每个数组有n个元素，数组内部已经有序，怎样将他们合并成一个大的有序数组？
方法1：
把每个数组的第[0]个取出来，比较k-1次可以取得最小值，将最小值赋给大数组的第[0]个，下标自增1，
然后每个数组从[0]到[n-1]循环，最终取完所有元素，这是一个很朴素的方法。时间复杂度是 O(kn) 。
选择最小值的部分类似于直接选择排序，复杂度是O(k)，那么很容易联想到把直接选择改为堆排序（方法2），复杂度就可以从O(k)降到O(logk)了，堆排序在前面的文章已经写过了，下面看2种新的选择方法。
2.1、胜者树(方法3)
胜者树的叶子节点保存的是待排序数据，非叶子节点保存的是数据的下标。
从网上搜得一张图片：
待排序数据之间可以两两比较，两个元素比赛（比大小），一个胜一个负，胜者写入父节点，如此循环一直到根节点，根节点保存着全部数据中的最终胜利者（最小值或最大值）。
根节点的值值是最小值的下标，将最小值取出保存，再给该节点赋一个大于所有数据的值，然后从该节点重新调整树。每次选出一个最小值，就调整一次胜者树。
胜者树，如果一个节点的值改变了，只需要沿着从该结点到根结点的路径调整树，而不必改变其他比赛的结果。
写代码前需要先观察并计算下标与数据的对应关系式。
#define MAX 9999
void adjust(int leaves[], int index_tree[], int k, int i)
{
int left, right; // 左右子结点
if(2 * i <= k)
left = index_tree[2 * i];
else
left = 2 * i - k - 1;
if(2*i+1 <= k)
right = index_tree[2*i+1];
else
right = 2 * i - k ;
index_tree[i] = leaves[left] > leaves[right] ? right : left; // 胜负判定
}
void winner_tree_sort(int data[], int n)
{
int* leaves = (int *)malloc((n)*sizeof(int)); // leaves 从 [0] 到 [n-1] 一个 n 个
int* index_tree = (int *)malloc((n)*sizeof(int)); // index_tree 从 [1] 到 [n-1] 一共 n-1 个
for(int i = 0;i < n; ++i) // 初始化叶子节点
leaves[i] = data[i];
for(int father = n-1; father > 0; --father)
adjust(leaves, index_tree, n-1, father);
for(int i = 1; i < n; ++i) // 选择n-1次,每次用最大值替换掉冠军节点,并调整胜者树
{
data[i-1] = leaves[index_tree[1]];
leaves[index_tree[1]] = MAX; // 比所有数据都大的数
// 自下而上,对胜者树进行调整
for(int father = (index_tree[1]+n)/2; father > 0; father /= 2)
adjust(leaves, index_tree, n-1, father);
}
data[n-1] = leaves[index_tree[1]]; // 最后一个数据
free(index_tree);
free(leaves);
}
2.2、败者树(方法4)
败者树是胜者树的一种变体。
图片：
在败者树中，用父结点记录其左右子结点进行比赛的败者，而让胜者参加下一轮的比赛。败者树的根结点记录的是败者，需要加一个结点来记录整个比赛的胜利者。
败者树可以简化重构的过程，败者树的重构只需要与其父结点比较，而胜者树的重构还要与兄弟结点比较。
#define MIN -1 // 最小值
#define MAX 9999 // 最大值
void adjust(int win, int *index_tree, int *leaves, int n) // win 是需要调整的leaves的下标
{
int father = (win + n) / 2; // 得到 win 的在败者树上的父节点
while(father > 0) // 不断与父节点对比，直到败者树的根节点
{
if(leaves[win] > leaves[index_tree[father]])// 如果当前节点win(小的是胜者)大于父节点:win 记录胜者下标,父节点记录败者下标
{
SWAP_INT(index_tree[father], win)
}
father /= 2; // 得到败者树的上一个父节点，继续与当前胜者 win 比较
}
index_tree[0] = win; // 最终的胜者
}
void build(int *index_tree, int *leaves, int n)
{
leaves[n] = MIN; // 最后一位放 MIN
for(int i = 0; i < n+1; ++i)
index_tree[i] = n; // 所有败者树初始化为 MIN 的下标, 即全部初始化为胜者,后面会被败者填充
for(int i = 0; i < n; ++i)
adjust(i, index_tree, leaves, n);
}
void loser_tree_sort(int data[], int n)
{
int* index_tree = (int *)malloc((n+1)*sizeof(int)); // 败者树,ls[0]存放胜者，其余存放败者
int* leaves = (int *)malloc((n+1)*sizeof(int)); // 叶子节点存数据, 最后多出的一位放MIN
// 初始化叶子节点,把源数据拷贝到叶子节点
memcpy(leaves, data, n*sizeof(int));
build(index_tree, leaves, n);
int i;
for (i = 0; i < n-1; ++i) // 选择 n-1 次
{
data [i] = leaves[index_tree[0]]; // 取出 胜者
leaves[index_tree[0]] = MAX; // 赋一个最差的值
adjust(index_tree[0], index_tree, leaves, n); // 调整树
}
data [i] = leaves[index_tree[0]]; // 别漏了最后一个数
}
2.3、败者树k路归并
只需要把选择最小值的部分由直接选择改为败者树选择即可： 代码链接
