作者：[柒号华仔]个人信条：星光不问赶路人,岁月不负有心人。
个人方向：专注于5G领域，同时兼顾其他网络协议，编解码协议，C/C++，linux等，感兴趣的小伙伴可以关注我，一起交流。
1. 归并排序介绍
1.1 定义
谈到归并我们需要先认识“分治”，顾名思义，分治即分而治之，一个问题很复杂，那么我们把问题拆分为简单点的小问题，将小问题继续拆分，最后所需面对的都是最小问题。将这些最小问题解决掉，一步步合并为大问题，最后实现整个问题的解决。
归并排序是建立在归并操作上的一种有效，稳定的排序算法，它是采用分治法的一个非常典型的应用。将待排序数组分为两条线逐级拆分，将子序列进行排序，然后沿两条线逐级合并，得到完全有序序列。这种通过递归，层层合并的方法，称为归并。
1.2 基本原理
归并操作的工作原理如下：
- 将数组拆分两个等分数组，然后逐级往下进行等分拆分，直至成为长度为1的最小元素；
- 数组元素两两进行排序，这些两两排序的元素归并为新的子数组；这里两个归并起点有两个点，一个是初始数组首元素，一个是等分初始数组中间元素。
- 前后两个子数组进行排序合并，形成更大的子数组；
- 依次向上排序和合并，直至两条线均合并为一个有序数组；
- 将两个支线数组进行合并，得到最终的有序数组。
1.3 时间复杂度
假设数组元素个数为n，时间复杂度为T(n)，
将 n 个数的序列，分为两个 n/2 的序列，则：T(n) = 2T(n/2) + n
将 n/2 个数的序列，分为四个 n/4 的序列，则：T(n) = 4T(n/4) + 2n
将 n/4 个数的序列，分为八个 n/8 的序列，则：T(n) = 8T(n/8) + 3n
…
将 n/2k 个数的序列，分为2k个 n/2k 的序列，则：T(n) = 2kT(n/2k) + kn
当 T(n/2k) = T(1)时， 即n/2k = 1，转换为以2为底n的对数：k = log2n，把k带入到T(n)中，得：T(n) = n + nlog2n。
因此归并排序的时间复杂度就是O(nlogn)。
2. 代码实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void Merge(int* arr, int left, int right, int mid)
{
int *p = (int*)malloc((right - left + 1) * sizeof(int));
int *temp = p;
int L = left;
int R = mid + 1;
memset(p, 0, (right - left + 1) * sizeof(int));
while((L <= mid)&&(R <= right))
{
*p++ = arr[L] < arr[R]?arr[L++] : arr[R++];
}
while (L <= mid)
{
*p++ = arr[L++];
}
while (R <= right)
{
*p++ = arr[R++];
}
memcpy(arr + left, temp, (right - left + 1) * sizeof(int));
free(temp);
}
void MergeSort(int* arr, int left, int right)
{
if (left >= right)
return;
int mid = (left + right)/2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
Merge(arr, left, right, mid);
}
int main()
{
int arr[10] = { 3,6,9,2,1,4,8,7,5,10};
MergeSort(arr, 0, 9);
for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
printf("%d ", arr[i]);
}
return 0;
}
运行结果：
