- 前言
- 一、归并排序
- 二、归并实现
- 1. 实现细节
- 2. 具体代码实现
- 总结
前言
归并排序的定义
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。将两个的有序数列合并成一个有序数列，我们称之为"归并"
一、归并排序
归并排序也称为“二路归并”排序
- 思想：首先将所有的数据默认每个数字单独一个组，接下来两两合并（两个组），当所有的数据在同一个组内的时候，数据完全有序，则可以结束
- 步骤：对于原始数据，可以看作是两只手，两只手依次抓取数据
第一次两两合并：从左向右，左右两只手依次抓取两个数据，并将抓取的两个元素进行排序
第二次两两合并：还是从左向右，左右两只手依次抓取两个数据，将抓取的数据进行排序
…
第n次两两合并：直到所有的数据均在同一个组内，此时就可以停止抓取，这时也就说明数据已经排序完成
具体步骤如下图例子所示
废话不多说，直接上动图：
- 对于二路归并排序来说，其最重要的就是数组的划分，每次要“抓取”的数据，需要先将数据分组，然后两两抓取
- 需要知道总共合并几次，对于一组数据，合并的次数怎样计算？
需要清楚的是，当所有的数据全部在同一个组内的时候，就停止抓取数据
例如：
其中，1 1 代表第一次抓取的值的个数，假设10个数据分为10个组，第一次“左手”抓取1个值，“右手”抓取一个值；
2 2 代表第二次抓取的值得个数，第二次“左手”抓取两个值，“右手”抓取两个值，此时也是合法得
…
8 8 代表本次抓取得数据，“左手”有8个，右手可以抓取8个，此时要注意，这样抓取也是合法的，因为总共有10个数据，左手抓取8个数据之后还剩2个数据，此时右手就只需要抓取2个数据即可，并不需要完全抓取8个数据，只要将数据中得值抓取完成即可
16 16 代表本次“左、右手”均可以抓取16个数据，但是数组总共有10个数据，所以本次“左手”抓不满，也就是说明：此时数据已经存在于同一个组内，也就是已经排好序
【说明】在第n次抓取数据之后，每个“小组”的数据元素个数为2^n
对于二路归并排序来说，最重要的就是：每次分组抓取数据，如何实现分组抓取，也就是上面所说的“两两合并”，只要可以清楚的知道怎样两两合并，那么只需要用for循环控制两两合并的次数即可，因为每次两两合并均是相同的理论
代码如下：
//一次融合函数 时间复杂度O（n） 空间复杂度O（n）
void Merge(int arr[], int len, int gap)
{
int low1 = 0;
int high1 = low1+gap-1;
int low2 = high1+1;
int high2 = low2+gap-1
while(low1<=high1 && low2<=high2)//保证两个组内还有数据去拿来比较
{
if(arr[low1] <= arr[low2])
{
brr[i++] = arr[low1++];
}
else
{
brr[i++] = arr[low2++];
}
}
//此时，肯定有一个手抓的组为空了，需要判断一下哪个手，做对应的出来
while(low1 <= high1)//左手没空，此时将左手数据向brr中挪动
{
brr[i++] = arr[low1++];
}
while(low2 <= high2)//右手没空，此时将右手数据向brr中挪动
{
brr[i++] = arr[low2++];
}
//此时应该，继续向后抓两个组
low1 = high2+1;
high1 = low1+gap-1;
low2 = high1+1;
high2 = low2+gap-1
brr[i++] = arr[low1++];
}
//最后将brr中的数据全部重新覆盖到arr里，即可
for(int i=0; i
arr[i] = brr[i];
}
free(brr);
}
清楚了怎样“两两合并”，只需要对其使用for循环控制两两合并的次数即可
//归并排序
void MergeSort(int *arr, int len)
{
for(int i=1; i
Merge(arr, len, i);
}
}
总结
- 归并排序是稳定的，因为其不涉及跳跃交换数据
【注】稳定性：如果排序之前 3在3‘ 的前面，但是在排序之后，3跑到了3’ 的后面，则认为它不稳定 - 时间复杂度：O(nlogn)
- 空间复杂度：O（n）
