C语言数据结构：归并排序详解
归并排序
有序数组合并原理
假设我们有两个已排序的数组arr1和arr2，创建一个能容纳两者总元素数量的新数组arr。使用三个指针分别指向arr1、arr2和arr的起始位置。比较两个数组中指针所指元素的值，将较小者放入arr，并移动对应的指针。当其中一个数组遍历完毕，将另一个数组的剩余元素直接复制到arr中。
当arr2遍历完毕后，将arr1剩余数据全部复制到arr中。
这种方法保证了合并后的数组仍然有序。那么，能否利用这一特性设计排序算法呢？
一个无序数组可以被分为左右两半。
如果这两半本身都是有序的，合并后即为有序数组。对于多数无序数组，无法直接找到这样的分界。但如果数组只包含两个元素呢？它们必定是有序的。
对于一个含四个元素的数组，可以递归拆分为单个元素的子序列：
这些原子序列都有序，然后将它们两两合并，生成有序子序列。不断合并，最终得到完整的有序数组。这就是归并排序的核心思想：先将数组拆分为若干长度为1的有序子序列，再逐步合并。
拆分阶段（"归"）
如同古代哲学中的"日取其半"，我们将一个数组不断二分，直到每个子序列只含一个元素。
合并阶段（"并"）
从长度为1的子序列开始，将相邻的两两合并成有序序列，直到所有子序列归并成一个数组。
归并排序实现
归并排序算法描述：设初始序列有n个记录，视其为n个长度为1的有序子序列。两两归并后，得到⌈n/2⌉个长度为2或1的子序列。重复此过程，直到获得一个长度为n的有序序列。
实现步骤：
- 将整个数组通过递归二分，直到子序列长度为1。
- 从递归堆栈底部开始合并有序子序列，再将合并结果拷贝回原数组。
递归分解过程层次分明，与二叉树类似。合并则是反向回溯。
递归版代码实现
void _MergeSort(int* data, int left, int right, int* temp)
{
if (left >= right)
return;
int mid = (left + right) / 2;
_MergeSort(data, left, mid, temp);
_MergeSort(data, mid + 1, right, temp);
int idx = left;
int p1 = left, p1End = mid;
int p2 = mid + 1, p2End = right;
while (p1 <= p1End && p2 <= p2End)
{
if (data[p1] <= data[p2])
temp[idx++] = data[p1++];
else
temp[idx++] = data[p2++];
}
while (p1 <= p1End)
temp[idx++] = data[p1++];
while (p2 <= p2End)
temp[idx++] = data[p2++];
for (int i = left; i <= right; i++)
data[i] = temp[i];
}
void MergeSort(int* data, int length)
{
int* temp = (int*)malloc(sizeof(int) * length);
_MergeSort(data, 0, length - 1, temp);
free(temp);
}
非递归版归并排序
归并排序的递归不会导致过深堆栈，递归版本简洁易读。非递归版本则扩展思维，用迭代模拟拆分和合并。
核心思路：引入变量gap表示子序列最大长度，初始为1。当gap=1时，数组被分为多个单元素子序列。两两合并后，子序列长度变为2。gap翻倍，重复合并。直到gap大于等于数组长度。
gap取值符合2^n，每轮合并后加倍，模拟递归的层次拆分。
非递归版代码实现
void MergeSortNonRecursive(int* data, int length)
{
int* temp = (int*)malloc(sizeof(int) * length);
int gap = 1;
while (gap < length)
{
for (int start = 0; start < length; start += 2 * gap)
{
int leftBegin = start;
int leftEnd = leftBegin + gap - 1;
int rightBegin = leftBegin + gap;
int rightEnd = rightBegin + gap - 1;
// 越界处理
if (leftEnd >= length)
break;
if (rightEnd >= length)
rightEnd = length - 1;
int idx = start;
int p1 = leftBegin, p1End = leftEnd;
int p2 = rightBegin, p2End = rightEnd;
while (p1 <= p1End && p2 <= p2End)
{
if (data[p1] <= data[p2])
temp[idx++] = data[p1++];
else
temp[idx++] = data[p2++];
}
while (p1 <= p1End)
temp[idx++] = data[p1++];
while (p2 <= p2End)
temp[idx++] = data[p2++];
for (int i = start; i <= rightEnd; i++)
data[i] = temp[i];
}
gap *= 2;
}
free(temp);
}
