归并排序的非递归实现
凱廸bob 人气:0归并排序的非递归实现 merge sort
归并排序也称为合并排序，本文详细介绍归并非递归的实现。
问题描述
有一串乱序的数字，将它们（利用合并排序的思想）排列成有序的。
通常使用一个数组来保存这个串无序的序列，输出也用一个数组来表示
输入：乱序的数组A，数组的长度n
输出：有序的数组A
特殊情形(元素个数为2i)
基本思路：看作是一颗倒过来的满二叉树，两两成对
这张图叙述了合并排序算法的基本思路，类似一棵倒放的二叉树。
图中标记的解释：state0代表初始的状态，经过第一趟合并（merge1）之后得到的状态为State1，以此类推。
归并排序的基本思路
-
在State0初始状态时，两两合并，合并用到的算法是“合并有序的数组 merge sorted array”。即每次合并得到的都是有序的数组。
两两合并的规则是：将两个相同序列长度的序列进行合并，合并后的序列长度double。
第一趟合并（merge 1）调用了4次merge sorted array，得到了4个有序的数组："5, 8"，"3, 9"，"6, 4"，"1, 4"（每个合并后的序列长度为2）
第二趟合并（merge 2）调用了2次merge sorted array，得到了2个有序的数组："3, 5, 8, 9"，"1, 4, 6, 11''（每个合并后的序列长度为4）
-
按步骤1的思想以此类推，经过多次合并最终得到有序的数组，也就是State3。
可以看出经过一共3趟合并，最终得到有序的数组。
可以看出每趟要执行的合并次数不同，第一趟合并执行4次，第二趟合并执行2次，第三趟合并行1次。
归并排序的循环体设计思路
看了上述的算法思想，可以知道算法可以设计成两层循环
- 外层循环遍历趟数
- 内层循环遍历合并次数
下面的伪码描述了两层循环体的实现：
1 merge_sort(A[], n) {
2 while (趟数条件) { // 外层循环：合并的大趟数
3 while (执行合并的条件) { // 内层循环：每趟合并的次数
4 // 进行两两合并
5 }
6 }
7 }
一般情形（数组的元素个数不一定是2i）
如图可知，一般数组元素的个数不一定是2i个。右边多出的"10, 7, 2"子树可以视作一般情况的情形。
虽然元素个数不一定是2i个，但是任意元素个数的n，必然可以拆分成2j + m个元素的情形（数学条件不去深究）
由图可知，特殊情形思想中的两两合并的规则不能满足一般情况的合并需求
- 图中灰色的箭头代表无需合并，因为找不到配对的元素。
- 图中墨蓝色的箭头代表两个长度不相等的元素也需要进行合
将上述的合并需求称为长短合并，容易知道长短合并仅存在1次或0次。
下面讨论的合并前/后的序列长度特指两两合并后得到的序列长度。
合并趟数的循环设计
虽然一般情形与特殊情形的合并规则有差别（一般情形复杂），但是可以设计一个通用的合并趟数条件。
设置变量t：记录每趟合并后序列的长度（t=2k），其中k是趟次（如图中的merge1、2、3、4）
- 通过观察发现：每次合并后序列的大小有规律，第一趟后合并的序列大小都是2，第二趟合并后的序列大小都是4，以此类推..
- "10, 7, 2"这三个元素组合而成的序列长度虽然不满足上述的规律，但是并不影响趟数的计算。24 = 16 ≥ 11，4趟后循环结束。
- 可以设计成：if 最后合并后的序列长度≥实际元素的个数n，这时可以说明循环结束
下面的伪代码给出了合并趟数的循环设计，以及循环结束的条件。
1 merge_sort(A[], n) {
2 int t = 1; // t：每趟合并后序列的长度
3 while (t<n) { // 合并趟数的结束条件是：最后合并后的序列长度t≥数组元素的个数n
4 t *= 2;
5 // TODO：每趟进行两两合并
6 }
7 }
每趟合并次数的循环设计
从上图可以看出：每趟的合并次数和元素的总数n有关，且和合并前/后的序列长度有关。
数组的元素总数n越大，自然需要合并的次数更多。
每趟合并前序列长度越长，这趟需要合并的次数更少。
设置变量s：记录合并前序列的长度
下面列出了一般情形下的合并数学规律
记m为两两合并的次数（图中每对黑色箭头代表一次两两合并）
记j为长短合并的次数（图中每对墨蓝箭头代表一次长短合并）
第一趟合并 ：n=11，s=1，t=2，m=5，j=0
第二趟合并 ：n=11，s=2，t=4，m=2，j=1
第三趟合并 ：n=11，s=4，t=8，m=1，j=0
第四趟合并 ：n=11，s=8，t=16, m=0，j=1
存在公式：m = n / t，j =(n % t > s ) ? 1: 0 可以设计如下的内层循环
其中第二个公式不太好理解，可以以merge2的合并过程作为参考：
两两合并得到了"3, 5, 8, 9"，"1, 4, 6, 11"两个序列后。还剩余3个元素，因为3>2=s，所以还要进行长短合并。
1 merge_sort(A[], n) {
2 int t = 1;
3 int i; // 每趟合并时第一个序列的起始位置
4 int s; // 合并前序列的长度
5 while (t < n) {
6 t *= 2;
7 i = 0;
8 s = t;
9 while(i + t < n) {// 每趟进行两两合并，结束条件：
10 // TODO：两两合并操作(对两个长度相等的数组进行合并)
11 i = i + t
12 }
13 if (i + s < n) { // 判断：还有两两长度不相同的数组需要合并
14 // TODO：长短合并操作(对于长度不相同的数组进行合并)
15 }
16 }
17 }
归并排序的完整代码
1 /**
2 * 归并排序算法
3 * @param A 乱序数组A
4 * @param n 数组A的元素个数
5 */
6 void merge_sort(int A[], int n) {
7 int i,s;
8 int t = 1;
9 while (t < n) { // 外层循环：合并的大趟数
10 s = t;
11 t *=2;
12 i = 0;
13 while (i + t < n) { // 内层循环：每趟需要合并的次数
14 merge(A, i, i+s-1, i+s*2-1, t);
15 i = i + t;
16 }
17 if (i + s < n) { // 判断还有剩下的元素待处理。
18 merge(A, i, i+s-1, n-1, n-i);
19 }
20 }
21 }
其中merge算法，请查看我的上一篇文章介绍：合并两个有序的数组。下面给出了实现：
1 /**
2 * 合并两个有序的子数组( A[p]~A[q]及A[q+l]~A[r]已按递增顺序排序 )
3 * @param A 整数数组
4 * @param p 第一个子数组的起始下标
5 * @param q 第一个子数组的末尾下标
6 * @param r 第二个字数组的末尾下标
7 * @param n A数组的元素个数
8 */
9 void merge(int A[], int p, int q, int r, int n) {
10 int *B = new int[n]; // 建立缓冲区
11 int k = 0; // 指向B的游标，主要用于插入数据进B中
12 int i = p, j = q + 1;
13 while (i <= q && j <= r) { // while循环的跳出条件是：i和j只要有一个超过各种数组的界限
14 if (A[i] >= A[j]) {
15 B[k++] = A[j++];
16 } else {
17 B[k++] = A[i++];
18 }
19 }
20 if (i == q+1) { // 说明是前半段先遍历完，把后半段的拼到数组后面
21 while (j <= r) {
22 B[k++] = A[j++];
23 }
24 } else {
25 while (i <= q) {
26 B[k++] = A[i++];
27 }
28 }
29 // 将选定的部分替换为B的数组
30 k = 0;
31 for (i = p; i <= r; i++) {
32 A[i] = B[k++];
33 }
34 delete[] B;
35 }
加载全部内容