排序算法中有一个是非常重要的算法思想,叫做合并算法(或归并算法,Merge Sort),这是一种分治思想,即将数组不断一分为二,然后再逐个合并排序。掌握这个思想以后就可以将复杂的问题不断简化,然后逐个击破。以下用Go语言来演示下具体实现。
实现步骤
1、先写一个合并已排序数组的函数,使两个数组合并后排序。
原理是不断遍历两个数组,比较其中最小的项,将小的项添加到新数组中,然后移动小项所在的数组指针,用下一个小的项再进行比较,直到数组被遍历完成为止。
2、再写一个合并排序的函数。这个函数是入口函数,主要是通过递归来不断拆分和调用合并函数。
其主要作用是:1)将数组不断一分为二,从外向里递归调用,直到子数组只剩下1个元素;2) 不断合并左右子数组,从内向外,直到递归执行完成,最终得到排序后的新数组。
3、验证程序。分别构造两组数据来验证,可以看到最后结果符合预期,新数组已经排好序。
领取专属 10元无门槛券
私享最新 技术干货