在上次分享的快排算法,不知大家感觉分享的如何,上次文章里面的图比较丑一点,快排的思想核心不知道大家有没有理解到位;我们今天继续给大家分享排序算法里面的另外一种排序算法:归并排序!
一、归并排序:
1、归并排序操作的核心思想:
a、确定分界点:mid=(l+r)/2
b、递归排序左边和右边(排完左右两边的数,就会成为两个有序的序列了)
c、归并(把上面的两个有序序列合并成一个有序的序列,用一个简单的词来说,就是合二为一!)
2、举例:
比如上图我们有两组已经排好的序列数字,我们要进行第三步合并,该如何进行呢?思路如下:
a、这里先定义一个空的数组res,它主要是为了临时存放合并序列排序好的数字;我们从图中可以看到,第一个序列指针i指向数字1,第二序列指针j指向2,这个时候我们要比较两个数字的大小,小的数字就放到临时数组res里面去,这里我们明显知道数字1小于2,所以把1放到临时数组res里取
b、然后指针i往下移动,如下图所示,再次进行比较,明显发现指针j指向的数字2更小,把它放到res里面去,然后指针j往下移动,指针i不动,后面依次类推