前言
归并排序, 是创建在归并操作上的一种有效的排序算法, 效率为 O(nlogn).1945 年由约翰. 冯. 诺伊曼首次提出. 该算法是采用分治法的一个非常典型的应用, 且各层分治递归可以同时进行.(引自维基百科)
原理
以上视频转自 https://www.youtube.com/watch?v=JSceec-wEyw
由于掘金中无法加载视频, 可以直接点击 YouTube(需 VPN)链接, 也可到我博客的原文链接中观看
用一张图片简单来说就是这样
示例代码(非递归)
- #include <stdio.h>
- #include <stdlib.h>
- #define MAXSIZE 100 // 用于要排序数组的最大值
- typedef struct // 定义一个顺序表结构
- {
- int r[MAXSIZE+1]; // 用于存储要排序数组, r[0]用作哨兵或者临时变量
- int length; // 用于存储顺序表的最大长度
- }SqList;
- void Merge(int *S, int *T, int low, int m, int high);
- void MergePass(int *S, int *T, int s, int length);
- void MergeSort(SqList *L);
- int main()
- {
- int i;
- int array[] = {39,80,76,41,13,29,50,78,30,11,100,7,41,86};
- SqList L;
- L.length = sizeof(array)/sizeof(array[0]); // 获取数组长度
- for(i=0;i<L.length;i++)
- L.r[i+1]=array[i]; // 把数组存入顺序表结构
- MergeSort(&L);
- for(i=0;i<L.length;i++) // 输出排序后的数组
- printf("%d",L.r[i+1]);
- return 0;
- }
- void MergeSort(SqList *L)
- {
- // 申请额外的空间, 由于 r[0]为哨兵, 所以这里长度要 + 1
- int* TR = (int *)malloc((L->length+1)*sizeof(int));
- int k = 1;/*k 用来表示每次 k 个元素归并 */
- while (k <L->length)
- {
- //k 每次乘以 2 是遵循 1->2->4->8->16... 的二路归并元素个数的原则
- MergePass(L->r, TR, k, L->length);/* 先借助辅助空间归并 */
- k *= 2;
- MergePass(TR, L->r, k, L->length);/* 再从辅助空间将排过序的序列归并回原数组 */
- k *= 2;
- }
- free(TR);// 释放内存
- TR=NULL;
- }
- // 将 S 中相邻长度为 s 的子系列两两归并到 T 中
- // 这段代码稍微难理解点, 文章后面会分析下
- void MergePass(int *S, int *T, int s, int length)
- {
- int i = 1; //r[0]用作哨兵或者临时变量
- int j;
- while (i <= length-2*s+1) //length-i+1(未合并元素)>= 2s
- {
- Merge(S, T, i, i+s-1, i+2*s-1);
- i= i+2*s; // 自增的下一个元素的起始点
- }
- if (i<length-s+1) // 归并最后两个序列
- Merge(S, T, i, i+s-1, length);
- else
- for (j = i; j <= length; j++)
- T[j] = S[j];
- }
- // 归并排序最主要实现函数
- // 将有序的 S[low..m]和 S[m+1..high]归并到有序的 T[low..high]中
- void Merge(int *S, int *T, int low, int m, int high)
- {//j 在 [m+1,high] 区间递增, k 用于目标 T 的下标递增, l 是辅助变量
- int j, k, l;
- for (k = low,j = m+1; low <= m && j <= high; k++) // 将 S 中的元素由小到大归并到 T 中
- {
- if (S[low] < S[j])
- T[k] = S[low++]; // 此处先执行 T[k] = S[low], 然后 low++;
- else
- T[k] = S[j++]; // 同理
- }
- //for 循环过后, 可能有 j>high 或者 low>m, 故分情况处理
- if (low <= m)
- {
- for (l = 0; l <= m-low; l++)
- T[k+l] = S[low+l]; // 将剩余的 S[low..m]复制到 T 中
- }
- if (j <= high)
- {
- for (l = 0; l <= high-j; l++)
- T[k+l] = S[j+l]; // 将剩余的 S[j..high]复制到 T 中
- }
}
这里对部分难以理解的代码做个详细分析:
- void MergePass(int *S, int *T, int s, int length)
- {
- int i = 1; //r[0]用作哨兵或者临时变量
- int j;
- while (i <= length-2*s+1) //length-i+1(未合并元素)>= 2s
- {
- Merge(S, T, i, i+s-1, i+2*s-1);
- i= i+2*s; // 自增的下一个元素的起始点
- }
- if (i<length-s+1) // 归并最后两个序列
- Merge(S, T, i, i+s-1, length);
- else
- for (j = i; j <= length; j++)
- T[j] = S[j];
}
第 5~9 行: 这里实现的是子序列的两两归并.
判断条件 i <= length-2*s+1 可以看做 length-i+1>= 2s, 表示未合并的元素小于 2s 时跳出循环, 即不足以构成两个长度为 s 的子序列时跳出循环;
未合并元素需要 + 1 的原因可以用个例子解释: 即第一次进入循环时, 应该是有 length 个元素未合并, 而 i 起始大小是 1, 所以这里要 + 1.
第 7 行: 传入元素 - 1 是因为 i+s 和 i+2s 都是下一个序列的起始点, 所以是一个序列的终点就是这两个值 - 1.
第 10~14 行: 判断条件 i<length-s+1 一样可以看做 length-i+1>s
满足条件: 未合并的元素长度大于 s, 表示还能构成一个长度为 s 的序列和一个小于 s 的序列, 即最后两个序列, 这时还要执行一次归并.
else: 未合并的元素长度小于 s, 则只剩一个序列, 这时无法归并, 直接把元素加到 T 数组后端.
剩下的应该不难理解了吧.
来源: https://juejin.im/post/5c2b41e55188256b9e0f2f0c