1. 目录
本节介绍两个最经典的排序算法之一的归并排序(另外个自然是快速排序了)
2.basic merge sort
将数列分成两份分别排序,然后最后再合并;这种分治思想递归的使用,就是归并排序了。
2.1 基本过程
基本过程如下:
2.2 实现
代码中的断言部分是为了方便调试用的。在运行程序的时候可以方便的开启或者关闭断言
注意点:不要在递归函数中使用辅助数组,频繁创建辅助数组会影响性能。
2.3 算法分析
根据提议得出比较次数的递归式
- 采用推导
- 采用归纳假设
2.4 in-place算法
定义如下:简单来说就是不需要额外的辅助内存空间的。(小于等于clogN的辅助空间仍然认为是in-place的)
2.5 归并排序优化
- 对于较小的排列对象,只使用插入排序就可以了,代码中是定义了CUTOFF变量来判断,何时使用插入排序
- 如果已经有序了,尽早返回
- 合并时交换辅助数组和原数组的角色
原本合并时都是合并到原数组,现在合并合并到辅助数组,这样可以减少每次递归时的拷贝数据到辅助数组的操作!
3. bottom-up merge sort
自底向上的归并算法,可以观察下图的过程与之前basic merge sort的图的区别,自底向上一开始就将整体分成小的自序列不断地归并;而基本归并算法则先左边的归并,再右边的归并。虽然从最本质上来讲,他们的子操作都是归并小的自序列,只不过归并子序列的时序不同。(个人理解)
3.1 基本过程
3.1 实现
可以看到自底向上的归并排序实现上可以不采用递归,通过一个增量来控制递归子序列大小。 merge方法的代码和前面的相同
3.2 使用比较器comparator
3.3 稳定性
主要记住稳定的排序,剩下的就是不稳定的, 稳定的是冒泡、插入、基数、归并。缩写为IRMB(insert,radix,merger,bubble),“爱人民币”
插入排序:比较局部有序序列时候不移动相同的数,稳定
选择排序:选择最小的时候涉及交换,可能交换时导致相同的数之间的位置变化,不稳定
希尔排序:也存在跨距离的交换,因此不稳定
归并排序:判断大小时,相等不移动,不会改变相对位置
练习题:
要去除重复的点,下面那种方法不好,第三种方法不好,因为最后Y坐标用快排会导致相同坐标的点分开:
例如:归并后如下
(1,8)
(2,8)
(2,8)
快排后可能如下:
(2,8)
(1,8)
(2,8)
4. 编程作业
这次的作业是共线问题。题目见:题目说明
题目要求用暴力破解,和基于排序的方法来处理;暴力破解的性能自然是比较差的
总结要点:
- 点需要进行编号,按照编号遍历
- 避免共线线段的重复计算,例如a->b->c->d和b->c->d