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


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

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

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

首先是一分为二:我们用这一串数据举个例子(小到大排):先将这一串数据对半分(下表中属于左半部分的标了1,右半部分标了2):
数组0(1)1(1)2(1)3(1)4(1)5(2)6(2)7(2)8(2)9(2)
a[]36187249105

然后按照那句话说的,分到不能分,那么我们就继续分:(数据对半除不尽用去尾法操作)
数组0(11)1(11)2(12)3(12)4(12)5(21)6(21)7(22)8(22)9(22)
a[]36187249105

继续分……
数组0(11)1(11)2(121)3(122)4(122)5(21)6(21)7(221)8(222)9(222)
a[]36187249105

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

接下来就是比较做排序。
首先我们进行第一层比较(两个数据比较),交换,完成后如下:
数组0(11)1(11)2(12)3(12)4(12)5(21)6(21)7(22)8(22)9(22)
a[]36178249510

第一次比较后是这样的。大家可以发现上方的角标有的从三位变成了两位。
接下来进行第二次比较,但此时是四个数据(或者两个和三个数据),那我们怎么比较呢?
我们用一组例子:大家看到带(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[]36178249510
指针位置






pq
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[]36178249510
指针位置






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[]36178249510
指针位置






p
q
result[]59







比较过程










第三步,右边还有10没有加入result数组中,所以我们要将剩下没排序的数字依次按顺序加入result数组中:
数组0(11)1(11)2(12)3(12)4(12)5(21)6(21)7(22)8(22)9(22)
a[]36178249510
指针位置






p
q
result[]5910






比较过程











最后一步,result数组重新填入a[]中:
数组0(11)1(11)2(12)3(12)4(12)5(21)6(21)7(22)8(22)9(22)
a[]36178245910
指针位置






p
q
result[]5910






比较过程











这就是如何多个数比较排序的方法,我们再看一个例子。此时已经是最后一次合并了(如下表,此时剩余最后一步,将左边的0~4号与右边的5~9号进行合并,从而排好序):
我们将p和q都指向两边的第一号,0号和5号,并且result清空。
数组0123456789
a[]13678245910
指针位置p



q



result[]









比较过程











第一次比较,发现1<2,将1加入result数组,p往后进一位。
数组0123456789
a[]13678245910
指针位置
p


q



result[]1








比较过程










第二次比较,发现3>2,将2加入result数组,q往后进一位。
数组0123456789
a[]13678245910
指针位置
p



q


result[]12







比较过程










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



p


q
result[]12345678

比较过程











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

数组0123456789
a[]13678245910
指针位置



p


q
result[]12345678910
比较过程











最后将result数组的值重新加入a[]中,
数组0123456789
a[]12345678910
指针位置









result[]









比较过程











那么这就是归并排序的步骤,不难理解,而且掌握方法后写程序就很有思路了。
已有 2 人购买  本主题需向作者支付 2 鱼币 才能浏览 购买主题

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

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

大佬厉害,论坛有你更精彩
页: [1]
查看完整版本: 归并排序(仅代码部分付费)