1. 目录

本节介绍两个最经典的排序算法之一的归并排序(另外个自然是快速排序了)

2.basic merge sort

将数列分成两份分别排序,然后最后再合并;这种分治思想递归的使用,就是归并排序了。

2.1 基本过程

基本过程如下:

2.2 实现

代码中的断言部分是为了方便调试用的。在运行程序的时候可以方便的开启或者关闭断言

注意点:不要在递归函数中使用辅助数组,频繁创建辅助数组会影响性能。

2.3 算法分析

根据提议得出比较次数的递归式

  1. 采用推导

  2. 采用归纳假设

2.4 in-place算法

定义如下:简单来说就是不需要额外的辅助内存空间的。(小于等于clogN的辅助空间仍然认为是in-place的)

2.5 归并排序优化

  1. 对于较小的排列对象,只使用插入排序就可以了,代码中是定义了CUTOFF变量来判断,何时使用插入排序

  1. 如果已经有序了,尽早返回

  2. 合并时交换辅助数组和原数组的角色
    原本合并时都是合并到原数组,现在合并合并到辅助数组,这样可以减少每次递归时的拷贝数据到辅助数组的操作!

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. 编程作业

这次的作业是共线问题。题目见:题目说明
其他参考资料1
其他参考资料2

题目要求用暴力破解,和基于排序的方法来处理;暴力破解的性能自然是比较差的

总结要点:

  1. 点需要进行编号,按照编号遍历
  2. 避免共线线段的重复计算,例如a->b->c->d和b->c->d