归并排序算法的思路及C代码实现
1. 概念
归并排序（Merging Sort)本质就是将K个有序的组合合并起来，简称K-路归并，分别取K个组合的首元素，进行K-1次比较，确定出最大或最小的元素放入第一位，随后再取该首元素的下一位再次组成K个元素进行k-1次比较，确定第二位元素，依次类推...直到所有元素比较后成为整体有序的组合。一般2-路归并最为简单和常用。下面以2-路归并顺序存储结构为例
时间复杂度：O(nlog2n)
空间复杂度：O(n)
算法稳定性：属于稳定结构，可适用于链式结构
2. 算法要点
Merge函数进行对两个有序组合进行排序，这个较为简单，依次比较两个首元素大小，谁大谁放入首元素即可MergeSort函数用到了递归的思想，将一个无序组合分为两个左右无序组合，分别对左右无序组合再调用MergeSort函数，直到该左右无序组合仅有一个元素为止（此时组合必然有序，一个元素嘛），最后再调用Merge函数，使左右有序组合合并。
3. 完整代码参考（C语言）
#include <stdlib.h>
#define MAXSIZE 10 // 静态顺序表最大长度
typedef int ElemType; // 假设数据类型为int类
typedef struct { // 静态顺序表数据元素
ElemType data[MAXSIZE]; // 数据项
int length;
}SqList;
void initList(SqList* L) { // 初始化顺序表
L->length = MAXSIZE;
for (int i = 0;i < L->length;i++) {
L->data[i] = rand(); // 随机初始化数据
}
}
void printData(SqList* L) {
for (int i = 0; i < L->length; i++) {
printf("%d ", L->data[i]);
}
puts();
}
void Merge(SqList* L, SqList* Li, int low, int middle, int high) { // 合并给定的两个有序数组
int m, n, j; // m,n分别指向左右两数组将比较元素的位置,j表示将要插入的位置
for (int i = low;i <= high;i++) { // 将待排序的两个数组复制到辅助数组里
Li->data[i] = L->data[i];
}
for (j = low, m = low, n = middle + 1;m <= middle && n <= high;j++) {
if (Li->data[m] <= Li->data[n])
L->data[j] = Li->data[m++];
else
L->data[j] = Li->data[n++];
}
while (m <= middle) L->data[j++] = Li->data[m++];
while (n <= high) L->data[j++] = Li->data[n++];
}
void MergeSort(SqList* L, SqList* Li, int low, int high) { // 合并排序算法
if (low < high) { // 当左或右只剩一个数据时直接合并即可
int middle = (low + high) / 2; // 找到中间位置分开
MergeSort(L, Li, low, middle); // 处理左半区域
MergeSort(L, Li, middle + 1, high); // 处理右半区域
Merge(L, Li, low, middle, high); // 合并左右有序区域
}
}
void main() {
SqList L;
initList(&L);
printData(&L);
SqList Li; // 辅助顺序表，用于保存归并前的元素
int low = 0, high = L.length - 1;
MergeSort(&L, &Li, low, high);
printData(&L);
}
4.后记
学习归并排序使跟着王道视频看的，里面也是讲了顺序存储结构下的归并排序，但是严蔚敏老师编写的数据结构上提到说也支持链式结构，且不用开辟辅助空间（及上面代码里的序列副本），网上搜索一下大概思路是：
- 利用链表的快慢指针（即有两个指针，快指针每次走两个节点，慢指针每次走一个节点，当快指针走到链表尽头时，慢指针才走到了链表的一半，此时就是我们想要的中间节点）找到链表的中心位置，然后将链表分为两个左右链表
- 再分别对其调用
MergeSort将其再化为左右链表，直到链表快慢指针相同为止（此时可确定链表仅余一个节点位置，可以直接合并） - 最后调用
Merge函数，将左右有序链表合并。 - 至于不用开辟辅助空间，是因为链表以指针相连，可以生成一个新的链表将合并后的有序指针相连，因为没用复制具体数据，仅保留了指针，所以应该不占空间。
纯属个人理解，参考了稍许资料，希望大家批评指正。