归并排序
介绍
归并排序和快速排序一样，都是基于分治思想的应用。
通过递归，不断将原数列分为两个数列，然后再分别使其有序，最后通过归并将两个有序子数列合并为新的有序数列。
值得注意的是，与快速排序不同，归并排序是稳定的。
代码实现
void merge_sort(int a[], int l, int r)
{
if (l >= r) return;//判断区间数据个数，为1则返回
int tmp[100001];//创建临时数组
int mid = l + r >> 1;
merge_sort(a, l, mid);
merge_sort(a, mid + 1, r);
int k = 0, i = l, j = mid + 1;//建立双指针
服务器托管网while (i 思路分析
void merge_sort(int a[], int l, int r)
{
if (l >= r) return;//判断区间数据个数，为1则返回
int tmp[100001];//创建临时数组
int mid = l + r >> 1;
merge_sort(a, l, mid);
merge_sort(a, mid + 1, r);
和快速排序先排序后递归不同，归并排序是先递归，无限细分，重点在于回溯时的归并，当递归到数组区间内只有1个数据时，肯定是有序的，经过归并后返回的数组肯定也是有序的，所以我们这里假设这个函数已经能够实现目的，将一个数组分为两部分然后分别排序，只需要用标记区间的起始位置和结束位置，而两个区间的分界就是mid，而归并的时候我们需要一个临时存放数据的临时数组tmp[]。
int k = 0, i = l, j = mid + 1;//建立双指针
while (i 这里便是整个算法最关键的地方：数组的归并。
首先，我们知道，两个区间已经分别有序，而第一个区间起点便是本次函数传入的起点l，终点为中值mid，第二个区间起点为mid+1，终点为函数传入的终点参数r。
我们创建双指针li和j，初始位置分别指向两个取件的起始位置，不断互相比较，值更小的放入数组然后往后遍历，这样就能实现整个数组的归并，值得注意的是，我们的判断条件为if(a[i]，这样，就能保证同样大小的数据按照原先的顺序依次进入临时数组，实现归并排序的稳定性。
最终，当其中一个指针遍历到区间结尾时，结束循环。
while(i当然，我们还需要将另外一个区间剩下的数据依次挤入临时数组，实现最终的排序，那我们就通过比较指针和终点的值来实现。
最后将排好的数据从临时数组中依次赋给原数组。
至此，我们完成了整个归并排序算法的闭环，完成了功能的实现。
结尾
归并排序和快速排序都是分治思想的体现，他们的思路不仅仅能拿来排序，也能解决一些具体问题，具体选择哪一种算法，就要依靠你细致入微的观察，结合题目的特性。
最后，归并排序和快速排序的时间复杂度一样，都是O(nlogn)。
以上便是对归并排序的介绍，本文由凉茶coltea撰写，思路来自AcWing，大佬yxc的课程。
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.服务器托管网fwqtg.net
本文为阿里云智能媒体服务IMS「云端智能剪辑」实践指南第四期，通过运用官方提供的花字模版或自定义设计花字，完成丰富、精美的花字特效视频剪辑。 昱尘｜作者 在视频后期剪辑中，“花字”是一种特别的存在。 通过使用适合视频的花字，不仅可以丰富视频内容，还可以让视频传…
