排序系列归并 /timsort

发布于: 2020 年 05 月 05 日

姗姗来迟的排序算法的第四篇,本介绍归并排序算法,是不是有人会问这样的问题,现在书本上学习到的排序算法都太经典了,在实际生产环境中基本上不会直接拿来使用,如果你的上司让你实现一个归并或者快排在生成环境中使用,那他一定是疯了,基于此,我介绍一种在归并排序算法基础上改进而来的Timsort算法,后者是在实际排序中经常用到的排序算法,与之详情,请往下看。



归并排序



归并排序的核心思想就是,将一个排序数组不断的划分,划分到足够的小的粒度,那就是长度为1了,然后开始1/1合并为2,然后再2/2合并为4,依次类推,在合并的过程中,让数据有序,最后完成排序,代码如下:

public static void sort(int[] nums, int start, int end) {
Arrays.nonBlank(nums);
if (start >= end) return;
int mid = (start + end) / 2;
sort(nums, start, mid);
sort(nums, mid + 1, end);
merge(nums, start, mid, end);
}
private static void merge(int[] nums, int start, int mid, int end) {
int[] temp = new int[end - start + 1];
int k = 0;
int i = start;
int j = mid + 1;
while (i <= mid && j <= end) {
if (nums[i] <= nums[j]) temp[k++] = nums[i++];
else temp[k++] = nums[j++];
}
while (i <= mid) temp[k++] = nums[i++];
while (j <= end) temp[k++] = nums[j++];
for (int l = 0; l < temp.length; l++) {
nums[start + l] = temp[l];
}
}

归并算法的主要方法还是分治法,然后合并分开的元素,直至最后有序,最好/最坏时间复杂度为O(nlgn),毋庸置疑,归并排序是稳定的排序,为什么有序,因为它没有跳跃,所以是有序的。



归并的时间复杂度提升了很多,那问题来了,归并排序有没有不足?是存在的,首先很容易想到的一个特例就是如果一个数组是有序的,那排定有序数组的时间复杂度也是O(nlgn),而如果用我们之前介绍的冒泡的改进算法只需要O(n)就搞定了,那下面分析一下如何改进归并排序算法。



已经看过归并排序的实现,会发现其实所有的工作都是在合并(merge)的过程当中完成的。所以归并的优化也就是对合并过程的优化,以下三点可能的优化途径:



1、能否使合并过程运行的更快?2、能否执行更少的合并过程?3、是否存在一些与其使用归并排序不如使用其他排序的情况?



基于以上三个问题,思考十分钟(这十分钟估计也想不出个啥),开始介绍下一种TimSort的自适应归并排序算法;



自适应归并排序算法——TimSort



TimSort算法基于归并算法改进而来的算法,其主要改进是:



  1. 在应用归并排序时,会寻找数组中的自增分区或者自减分区,已分区为合并的基础长度,而不是将其划分单个的元素;

  2. 针对自减分区直接进行翻转而不是直接合并,自减分区识别中必须严格降序,要不然无法保证算法的稳定性;

  3. 在分区合并时,采用二分插入算法,即使用二分查找找到数据插入的位置,然后插入;

  4. 当部分分区(TimSort中把分区成为run)长度小于分区最小长度时,从数组中选择合适的长度插入;

  5. 当数组的长度小于某一特定值时,其直接采用插入排序来排序

  6. 算法采用栈来存放有序分区,其合并时机要符合一定规则,假设从栈顶到栈底,分别有x/y/z三个元素(分区),当x>y+z && y>z时,合并结束,否则进行合并操作;

  7. 合并过程中,采用二分插入算法提高效率;



基于以上所有的改进策略,TimSort排序算法诞生,其使用场景是序列连续部分有序,当然其最坏的表现也不过就是普通归并,不能比这个更坏了,其最好时间复杂度O(n),其平均/最坏时间复杂度O(nlgn),并且该算法为稳定排序。具体实现参见 java1.7+版本中的Arrays.sort方法,另外python中的排序算法也是这个。



总结



归并算法其时间复杂度很稳定,其最好/平均/最坏时间复杂度是一样,这样给出了改进的空间,映射到生活中好像也是如此,我们也得根据某些特殊情况去制定一些特殊的规则,必须不是所有的人都想走大路,有时候符合条件的小路也未尝不是一种很好的选择。



发布于: 2020 年 05 月 05 日 阅读数: 34
用户头像

还未添加个人签名 2020.02.06 加入

还未添加个人简介

评论

发布
暂无评论
排序系列归并/timsort