易语言归并排序

2. 从上往下的归并排序:它与"从下往上"在排序上是反方向的。它基本包括3步:
① 分解 -- 将当前区间一分为二,即求分裂点 mid = (low + high)/2;
② 求解 -- 递归地对两个子区间a[low...mid] 和 a[mid+1...high]进行归并排序。递归的终结条件是子区间长度为1。
③ 合并 -- 将已排序的两个子区间a[low...mid]和 a[mid+1...high]归并为一个有序的区间a[low...high]。
下面的图片很清晰的反映了"从下往上"和"从上往下"的归并排序的区别。(以下资料来自:skywang12345)

511遇见

511遇见

通过"从上往下的归并排序"来对数组{80,30,60,40,20,10,50,70}进行排序时:
1. 将数组{80,30,60,40,20,10,50,70}看作由两个有序的子数组{80,30,60,40}和{20,10,50,70}组成。对两个有序子树组进行排序即可。
2. 将子数组{80,30,60,40}看作由两个有序的子数组{80,30}和{60,40}组成。
将子数组{20,10,50,70}看作由两个有序的子数组{20,10}和{50,70}组成。
3. 将子数组{80,30}看作由两个有序的子数组{80}和{30}组成。
将子数组{60,40}看作由两个有序的子数组{60}和{40}组成。
将子数组{20,10}看作由两个有序的子数组{20}和{10}组成。
将子数组{50,70}看作由两个有序的子数组{50}和{70}组成。

511遇见

通过"从下往上的归并排序"来对数组{80,30,60,40,20,10,50,70}进行排序时:
1. 将数组{80,30,60,40,20,10,50,70}看作由8个有序的子数组{80},{30},{60},{40},{20},{10},{50}和{70}组成。
2. 将这8个有序的子数列两两合并。得到4个有序的子树列{30,80},{40,60},{10,20}和{50,70}。
3. 将这4个有序的子数列两两合并。得到2个有序的子树列{30,40,60,80}和{10,20,50,70}。
4. 将这2个有序的子数列两两合并。得到1个有序的子树列{10,20,30,40,50,60,70,80}。

算法步骤

1、申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;

2、设定两个指针,最初位置分别为两个已经排序序列的起始位置;

3、比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;

4、重复步骤 3 直到某一指针达到序列尾;

5、将另一序列剩下的所有元素直接复制到合并序列尾。

511遇见

下面借助分而治之的文章加深理解

511遇见

可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程,递归深度为log2n。(以下资料来自:分而治之)

合并相邻有序子序列

再来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。

511遇见

511遇见

易语言实现归并排序

借助前面的资料,我们已经对归并有一个简单的了解,并且感性的知道了分治的方法,下面易语言来实现,难度教大:

merge

.版本 2
.子程序 merge, , , 归并排序(从上往下)代码
.参数 start, 整数型, , 左位置,1个有序区间的起始地址。
.参数 end, 整数型, , 右位置第2个有序区间的结束地址。
.参数 mid, 整数型, , 中间位置第1个有序区间的结束地址。也是第2个有序区间的起始地址。
.参数 stb, 逻辑型
.参数 a, 整数型, 参考 数组
.局部变量 i, 整数型
.局部变量 j, 整数型
.局部变量 k, 整数型
.局部变量 temp, 整数型, , "0", tmp是汇总2个有序区的临时区域
i = start  ' 第一个有序区的索引
j = mid + 1  ' 第二个有序区的索引
k = 0  ' 临时区域的索引
重定义数组 (temp, 假, 取数组下标 (a, ))
.判断循环首 (i ≤ mid 且 j ≤ end)
    .如果 (stb)
        .如果 (a [i] < a [j])
            k = k + 1
            temp [k] = a [i]
            i = i + 1
        .否则
            .如果真 (a [i] ≠ a [j])
                rsvnum = rsvnum + mid + 1 - i
            .如果真结束
            k = k + 1
            temp [k] = a [j]
            j = j + 1
        .如果结束
    .否则
        .如果 (a [i] > a [j])
            k = k + 1
            temp [k] = a [i]
            i = i + 1
        .否则
            .如果真 (a [i] ≠ a [j])
                rsvnum = rsvnum + mid + 1 - i
            .如果真结束
            k = k + 1
            temp [k] = a [j]
            j = j + 1
        .如果结束
    .如果结束
.判断循环尾 ()
.判断循环首 (i ≤ mid)
    k = k + 1
    temp [k] = a [i]
    i = i + 1
.判断循环尾 ()
.判断循环首 (j ≤ end)
    k = k + 1
    temp [k] = a [j]
    j = j + 1
.判断循环尾 ()
' // 将排序后的元素,全部都整合到数组a中。
.变量循环首 (start, end, 1, i)
    a [i] = temp [i - start1]
.变量循环尾 ()

mergesort

.版本 2
.子程序 mergesort, 整数型
.参数 array, 整数型, 参考 数组
.参数 l, 整数型, ,.参数 r, 整数型, ,.参数 sort, 逻辑型
.局部变量 mid, 整数型
.如果真 (l = r)
    返回 (0)
.如果真结束
mid = (l + r)2
mergesort (array, l, mid, sort)  ' 左边有序
mergesort (array, mid + 1, r, sort)  ' 右边有序
merge (l, r, mid, sort, array)  ' 合并两个有序数组
返回 (rsvnum)

归并排序

.版本 2
.子程序 归并排序, 整数型, 公开, 返回逆序对数量
.参数 array, 整数型, 参考 数组
.参数 sort, 逻辑型, , 真从小到大
.局部变量 l, 整数型
.局部变量 r, 整数型
l = 1
r = 取数组成员数 (array)
返回 (mergesort (array, l, r, sort))

测试

.版本 2
.支持库 spec
.局部变量 a, 整数型, , "0"
a = { 12, 33, 56, 89, 78, 521, -60, 1, 92, 11, -23, 89 }
调试输出 (归并排序 (a,))
调试输出 (a)

数组:12{-60,-23,1,11,12,33,56,78,89,89,92,521}


发布日期:

所属分类: 易语言 标签: