排序系列归并 /timsort
姗姗来迟的排序算法的第四篇,本介绍归并排序算法,是不是有人会问这样的问题,现在书本上学习到的排序算法都太经典了,在实际生产环境中基本上不会直接拿来使用,如果你的上司让你实现一个归并或者快排在生成环境中使用,那他一定是疯了,基于此,我介绍一种在归并排序算法基础上改进而来的Timsort算法,后者是在实际排序中经常用到的排序算法,与之详情,请往下看。
归并排序
归并排序的核心思想就是,将一个排序数组不断的划分,划分到足够的小的粒度,那就是长度为1了,然后开始1/1合并为2,然后再2/2合并为4,依次类推,在合并的过程中,让数据有序,最后完成排序,代码如下:
归并算法的主要方法还是分治法,然后合并分开的元素,直至最后有序,最好/最坏时间复杂度为O(nlgn),毋庸置疑,归并排序是稳定的排序,为什么有序,因为它没有跳跃,所以是有序的。
归并的时间复杂度提升了很多,那问题来了,归并排序有没有不足?是存在的,首先很容易想到的一个特例就是如果一个数组是有序的,那排定有序数组的时间复杂度也是O(nlgn),而如果用我们之前介绍的冒泡的改进算法只需要O(n)就搞定了,那下面分析一下如何改进归并排序算法。
已经看过归并排序的实现,会发现其实所有的工作都是在合并(merge)的过程当中完成的。所以归并的优化也就是对合并过程的优化,以下三点可能的优化途径:
1、能否使合并过程运行的更快?2、能否执行更少的合并过程?3、是否存在一些与其使用归并排序不如使用其他排序的情况?
基于以上三个问题,思考十分钟(这十分钟估计也想不出个啥),开始介绍下一种TimSort的自适应归并排序算法;
自适应归并排序算法——TimSort
TimSort算法基于归并算法改进而来的算法,其主要改进是:
在应用归并排序时,会寻找数组中的自增分区或者自减分区,已分区为合并的基础长度,而不是将其划分单个的元素;
针对自减分区直接进行翻转而不是直接合并,自减分区识别中必须严格降序,要不然无法保证算法的稳定性;
在分区合并时,采用二分插入算法,即使用二分查找找到数据插入的位置,然后插入;
当部分分区(TimSort中把分区成为run)长度小于分区最小长度时,从数组中选择合适的长度插入;
当数组的长度小于某一特定值时,其直接采用插入排序来排序
算法采用栈来存放有序分区,其合并时机要符合一定规则,假设从栈顶到栈底,分别有x/y/z三个元素(分区),当
x>y+z && y>z
时,合并结束,否则进行合并操作;合并过程中,采用二分插入算法提高效率;
基于以上所有的改进策略,TimSort排序算法诞生,其使用场景是序列连续部分有序,当然其最坏的表现也不过就是普通归并,不能比这个更坏了,其最好时间复杂度O(n),其平均/最坏时间复杂度O(nlgn),并且该算法为稳定排序。具体实现参见 java1.7+版本中的Arrays.sort方法,另外python中的排序算法也是这个。
总结
归并算法其时间复杂度很稳定,其最好/平均/最坏时间复杂度是一样,这样给出了改进的空间,映射到生活中好像也是如此,我们也得根据某些特殊情况去制定一些特殊的规则,必须不是所有的人都想走大路,有时候符合条件的小路也未尝不是一种很好的选择。
版权声明: 本文为 InfoQ 作者【脚动两轮男之漂流小王子】的原创文章。
原文链接:【http://xie.infoq.cn/article/b5bfb112e56389aed9ad67b9c】。文章转载请联系作者。
评论