1. 简介

本节主要讲元素的排序算法,目录如下

2. rules of the game

java中通过回调使用compareTo方法来达到比较的目的。

实数、字符串比较都满足一个全序关系:


下面的例子就不满足全序关系,因为其不满足传递性


这是rule of the game的课后习题,答案是以下的compareTo方法是不满足传递性的,因为在比较方法中引入了较大的影响因子EPS,这个在设计比较算法的时候值得注意。

补充资料:
全序关系的解释
偏序关系的解释

偏序和全序是公里集合论中的概念。

首先你要知道什么是二元关系。
比如实数中的“大小”关系,集合的集合中的“包含”关系就是两种二元关系。

所谓偏序,即偏序关系,是一种二元关系。
所谓全序,即全序关系,自然也是一种二元关系。

全序是指,集合中的任两个元素之间都可以比较的关系。比如实数中的任两个数都可以比较大小,那么“大小”就是实数集的一个全序关系。

偏序是指,集合中只有部分元素之间可以比较的关系。比如复数集中并不是所有的数都可以比较大小,那么“大小”就是复数集的一个偏序关系。

显然,全序关系必是偏序关系。反之不成立。

简单概括:全序关系就是所有元素都是可比较的,偏序关系则不然

2.初级排序算法以及补充知识

之前其实做过一些总结,欢迎查看:
各个排序算法总结

以下排序算法只做一些新的补充,具体可以参照之前的总结,这里不再赘述。

2.1 初级排序算法:选择排序、插入排序、SHELL排序

选择排序和插入排序的区别在于:选择每次会从右侧选出第i小的数,并且“固定”在左侧,选择出第i小的数后进行的交换是不相邻的,也是不稳定的;插入排序保证左侧的部分是“当前有序的”,每次i递增,会调整左侧的序列直到满足当前有序,是基于“插入”的,“插入”是基于左侧序列的相邻交换,因此是稳定的。

选择排序平均时间较好,插入排序对基本有序的数列排序排序性能较好。

两者都是O(n^2)

还有冒泡排序和插入排序的区别: 插入排序是在左侧当前有序序列内进行相邻交换,而冒泡排序则是每次对整个序列进行相邻交换

希尔排序的时间复杂度还没有完全被确定,包括合理的增量取值,一个有趣的算法。增量可以考虑取小于N的素数。时间复杂度取决于增量, 希尔排序的时间复杂度是:O(nlogn)~O(n2)

2.2 shufle

洗牌,例如将一个数组的值随机打乱就是shuffle的例子。

线性时间内可以完成这个事情(每个数在任意位置出现的概率相同)

采用这种Knuth shuffle算法即可,每次从0-i之间产生一个随机数作为随机索引的位置,与该位置的索引值交换即可。

错误的洗牌算法示范:

2.3 凸包

例子:凸包指的是能够将下面所有N个点围起来的点的集合


凸包的几何属性:

  1. 有一条逆时针回路
  2. Y坐标最低的点和其他凸包上的点构成的角的角度是越来越大的

Granham scan算法:

  1. 选取一个Y坐标最低的
  2. 将所有的点以P为坐标,按照角大小编号
  3. 开始从编号小的开始选取,发现不符合ccw(counter clock wise) turn的就抛弃,如图4号点不满足ccw

这里提出这个问题是因为解决这个问题需要很多排序算法,作者想说明好的排序算法也会带来的好的凸包问题解决算法

判断是否满足CCW,即判断当前的点是不是在前面所有点的左侧即可

计算几何学实现方式: