目录
归并排序
一、简介：
二、思路
三、代码
归并排序
一、简介：
归并，也叫合并，合二为一嘛，归并排序实际上相当于二叉树递归，先左右拆分，最后给数组拆分为每个数据为独立个体，再执行合并操作。
时间复杂度：O()-----口令：快（快速排序）以
归（归并排序）队（堆排序）
空间复杂度：O(n)因为需要临时数组几个数据，临时数组大小就是几个。口令--饿鬼（归并）炸鸡（基数排序）块
稳定性：稳定，因为归并的时候，优先归并前面那个范围的，相对位置不贵发生改变，
口令--稳稳的幸福，鸡（基数排序）毛（冒泡排序）插（直接插入和折半插入排序）龟（归并排序）壳
排序趟数：对N个元素进行K路归并，排序排序趟数t等于t=向上取整。
移动次数：N个元素，进行k路归并，移动元素个数为：N*
二、思路
归并排序主要分为两步：第一步，给数组左右拆分；第二步两两合并
第一步，给数组左右拆分：
- 给数组传进两个标记，表示数组范围，分别为low和high
- 当low<high时，计算mid中间标记，这样就给一个数组分为两个数组了mid为中间点
- 然后进入递归，左边递归数组范围时low和mid右边递归范围时mid+1和high。
- 就这样层层递归，递归到最后，每个数据都成叶子结点了，再执行归并操作，但一个元素时肯定有序，所以返回倒数第二层，执行归并操作，依次往上返。
- 步骤如图所示，但是，原理是图中从最下层开始递归，然后递归到最后，都递归成叶子结点了，返回倒数第二层开始第一次归并操作，开始两两合并，选大小。
第二步两两合并：
- 叶子结点时，归并操作没用，因为只有一个元素，肯定有序，因此往倒数第二层返回，执行倒数第二层的归并操作。
- 归并时，我们是传了三个坐标，low，mid和high。
- 先创建个临时数组，给原数组的数值复制进去，用来对比最大或最小值，
- 再定义一个实际坐标，指向实际数组中要存放的位置，
- 就这个要存放的位置，来个循环，每次循环的时候，进行low到mid这个范围和mid+1到high这个范围进行比对，然后二选一存放值。
- 如果最后两两没法对比了，再给剩下的都放进实际数组即可
三、代码
#include <stdio.h>
#include <malloc.h>
void PrintSort(int *a,int len)
{int i=0;for(i=0;i<len;i++){printf("%d ",a[i]);}printf("\n");
}
void Merge(int *a,int low,int mid,int high)
{int *b=(int*)malloc((high+1)*sizeof(int));int i;for(i=low;i<=high;i++){b[i]=a[i];//临时数组，存进去值，用来取值比较。 }//k为a数组实际指向的箭头 int k=low;//用p，q两个箭头分别指向b数组中两个紧挨着的有序数组，然后判断谁打谁小，随后给a[k]重新赋值 int p,q;//两数组对比，然后选出一个，赋值到a中，随后k++，a数组换下一个坐标接着重复 步骤 for(p=low,q=mid+1,k=low;p<=mid&&q<=high;k++){//在临时数组b中进行对比选择，最后赋值到实际数组a中 if(b[p]<=b[q]) {a[k]=b[p];p++;}else{a[k]=b[q];q++;}}//如果对比完，还有一个数组没有对比完，接着往后赋值即可。 while(p<=mid){a[k]=b[p];k++;p++; } while(q<=high){a[k]=b[q];k++;q++;}
}
void MergeSort(int *a,int low,int high)
{//归并排序是个递归过程，先从整体表，慢慢拆分 //拆分成每个数据是个整体时，再执行归并操作//两个合并成一个，依次往回返回if(low<high){int mid =(low+high)/2;MergeSort(a,low,mid);MergeSort(a,mid+1,high);Merge(a,low,mid,high);}
} int main()
{int a[7]={49,38,65,97,76,13,27};MergeSort(a,0,6);PrintSort(a,7);return 0;
}
