归并排序（仅代码部分付费）

bangbang-ande · 发表于 2023-7-17 10:10:17

[index]
[#1]原理部分
[#2]代码部分
[/index]
归并排序是重要的一个排序，归并排序的原理很有意思，请大家往下看。
有句话叫做大事化小，小事化了。归并排序也就是用的这一种非常简单的方法来排序的。

用一句话的概括叫做：将数据一分为二，分到不能分，然后根据比较大小的方法排序。
说起来很简单，但实际上做起来不简单，我们用一串数据来模拟一遍：

数组	0	1	2	3	4	5	6	7	8	9
a[]	3	6	1	8	7	2	4	9	10	5

这一串数据就是模拟数据了。接下来我们把刚刚讲的那句话拆解一下：
数据一分为二，分到不能分/然后用比较大小的方法排序
拆解后，会发现只有两个步骤：分+排序。

首先是一分为二：我们用这一串数据举个例子（小到大排）：先将这一串数据对半分（下表中属于左半部分的标了1，右半部分标了2）：

数组	0(1)	1(1)	2(1)	3(1)	4(1)	5(2)	6(2)	7(2)	8(2)	9(2)
a[]	3	6	1	8	7	2	4	9	10	5

然后按照那句话说的，分到不能分，那么我们就继续分：（数据对半除不尽用去尾法操作）

数组	0(11)	1(11)	2(12)	3(12)	4(12)	5(21)	6(21)	7(22)	8(22)	9(22)
a[]	3	6	1	8	7	2	4	9	10	5

继续分……

数组	0(11)	1(11)	2(121)	3(122)	4(122)	5(21)	6(21)	7(221)	8(222)	9(222)
a[]	3	6	1	8	7	2	4	9	10	5

此时你会看到，数据有一些在第二步就分成了两个一组，那么当分到两两一组或单独一组，就可以停止分组了。（如上表）这就叫做分到不能分，大家明白了吗？

接下来就是比较做排序。
首先我们进行第一层比较（两个数据比较），交换，完成后如下：

数组	0(11)	1(11)	2(12)	3(12)	4(12)	5(21)	6(21)	7(22)	8(22)	9(22)
a[]	3	6	1	7	8	2	4	9	5	10

第一次比较后是这样的。大家可以发现上方的角标有的从三位变成了两位。
接下来进行第二次比较，但此时是四个数据（或者两个和三个数据），那我们怎么比较呢？
我们用一组例子：大家看到带(22)中的例子，带(22)的有三个数，分别是9,5,10，它们在上一步分成了左右两边，分别是9在一边，5和10在另一边
然后我们命名两个变量p和q，作为指针（因为我不会写指针），将指针分别指向每一边的第一个数
然后我们在命名一个result数组，等会大家就知道它的作用了。
以上的过程均用表格呈现：

数组	0(11)	1(11)	2(12)	3(12)	4(12)	5(21)	6(21)	7(22)	8(22)	9(22)
a[]	3	6	1	7	8	2	4	9	5	10
指针位置								p	q
result[]
比较过程

第一步，我们先对p和q指针指向的数字对比，发现9>5，然后我们先将5加入result数组里，然后将q向后进一位，如下表：

数组	0(11)	1(11)	2(12)	3(12)	4(12)	5(21)	6(21)	7(22)	8(22)	9(22)
a[]	3	6	1	7	8	2	4	9	5	10
指针位置								p		q
result[]	5
比较过程

第二步，我们继续将和q指针指向的数字对比，发现10>9，那么我们将9加入result数组里，然后将p向后进一位。但你发现p向后没有办法进位了，那么排序就结束了。

数组	0(11)	1(11)	2(12)	3(12)	4(12)	5(21)	6(21)	7(22)	8(22)	9(22)
a[]	3	6	1	7	8	2	4	9	5	10
指针位置								p		q
result[]	5	9
比较过程

第三步，右边还有10没有加入result数组中，所以我们要将剩下没排序的数字依次按顺序加入result数组中：

数组	0(11)	1(11)	2(12)	3(12)	4(12)	5(21)	6(21)	7(22)	8(22)	9(22)
a[]	3	6	1	7	8	2	4	9	5	10
指针位置								p		q
result[]	5	9	10
比较过程

最后一步，result数组重新填入a[]中：

数组	0(11)	1(11)	2(12)	3(12)	4(12)	5(21)	6(21)	7(22)	8(22)	9(22)
a[]	3	6	1	7	8	2	4	5	9	10
指针位置								p		q
result[]	5	9	10
比较过程

这就是如何多个数比较排序的方法，我们再看一个例子。此时已经是最后一次合并了（如下表，此时剩余最后一步，将左边的0~4号与右边的5~9号进行合并，从而排好序）：
我们将p和q都指向两边的第一号，0号和5号，并且result清空。

数组	0	1	2	3	4	5	6	7	8	9
a[]	1	3	6	7	8	2	4	5	9	10
指针位置	p					q
result[]
比较过程

第一次比较，发现1<2，将1加入result数组，p往后进一位。

数组	0	1	2	3	4	5	6	7	8	9
a[]	1	3	6	7	8	2	4	5	9	10
指针位置		p				q
result[]	1
比较过程

第二次比较，发现3>2，将2加入result数组，q往后进一位。

数组	0	1	2	3	4	5	6	7	8	9
a[]	1	3	6	7	8	2	4	5	9	10
指针位置		p					q
result[]	1	2
比较过程

其余的比较同理，我们跳过……
最后一次比较，8<9，将8加入result数组，p往后进一位，但此时p已经是指向左边的最后一位了，那么停止循环。

数组	0	1	2	3	4	5	6	7	8	9
a[]	1	3	6	7	8	2	4	5	9	10
指针位置					p				q
result[]	1	2	3	4	5	6	7	8
比较过程

然后我们将没有排序的9和10也依次加入result数组：

数组	0	1	2	3	4	5	6	7	8	9
a[]	1	3	6	7	8	2	4	5	9	10
指针位置					p				q
result[]	1	2	3	4	5	6	7	8	9	10
比较过程

最后将result数组的值重新加入a[]中，

数组	0	1	2	3	4	5	6	7	8	9
a[]	1	2	3	4	5	6	7	8	9	10
指针位置
result[]
比较过程

那么这就是归并排序的步骤，不难理解，而且掌握方法后写程序就很有思路了。

购买主题 已有 2 人购买 本主题需向作者支付 2 鱼币 才能浏览

yinda_peng · 发表于 2023-7-17 11:14:15

loveKYF · 发表于 2023-11-17 10:42:01

大佬厉害，论坛有你更精彩

账号		自动登录	找回密码
密码			立即注册

[技术交流] 归并排序（仅代码部分付费）