2 排序

2.1初级排序算法

2.1.1游戏规则

2.1.1.2运行时间

排序成本模型

类型 说明
交换元素算法 计算比较和交换的数量
不交换元素 计算访问数组的次数

2.1.1.3额外内存使用

排序算法分类

类型 说明
原地排序算法 只需函数调用所需的栈和固定数目的实例变量
其他排序算法 需要额外内存空间存储数组副本

2.1.1.4数据类型

创建自己的数据类型时,只要实现Comparable接口就可以保证用例代码可以将其排序,只需要实现compareTo()方法定义目标类型对象的自然次序,从而实现主键抽象
v.compareTo(w)规则

v,w大小关系 方法返回值
v == w 0
v > w >0
v < w <0
无法比较/含有null 抛出异常

2.1.2选择排序

2.1.3插入排序

2.1.6希尔排序