- 排序算法运行时间：计算排序算法在不同随机输入下基本操作的次数（即比较和交换，若不需要交换，则比较访问数组的次数）
- 排序算法内存开销：
- 原地排序算法：除函数调用所需栈及固定数量的实力变量外无需额外内存开销；
- 其它排序算法：需要额外内存空间存储另一份数据副本
- Java中继承Comparable接口，重写compareTo()规定排序规则，从而实现自定义数据类型对象的排序比较（p155）
- 基本排序算法
- 选择排序：不断选取剩余数组中最值并进行交换按顺序排列
时间效率取决于排序次数
-
N*N／2次比较：
(N-1)+(N-2)+...+2+1 = N(N-1)/2 ~ N*N/2 N次交换
运行时间与输入无关，等长的顺序乱序数列排序时间相同
数据移动次数最少
- 插入排序：从a[1]起，逐项同其前面相邻已排序数据比较，按顺序交换并排列直至前方相邻数据比其小
- 排序时间效率取决于数组中初始顺序
- 最多NN/2次比较，最少N-1次比较，平均NN/4次
- 最多NN/2次交换，最少0次交换，平均NN/4次
- 交换次数与数组中倒置个数相同，比较次数不小于交换次数，不大于倒置个数加上N-1
- 对部分有序数组的排序非常有效
- 改进方法：每次比较后将较大元素向右移而不是交换，从而将访问数组的次数减半
-
希尔排序：快速的插入排序，将数组初始按间隔h(h>N/3)比较大小并交换，每轮排序完见效间隔h进行新一轮排序，直至h=1（此时即为部分有序数组的插入排序）
- h由小到大依此可为：1、4、13、40、121。。。，h初始值为1，第一轮循环比较初始值为h*3+1且h<N/3，每轮循环后h=h/3（.....40，13，4，1）
- 比插入排序效率高，尤其在数组较大时
- 运行时间小于N*N级
- 代码量小，不需要额外内存空间，算法较简单
- 选择排序：不断选取剩余数组中最值并进行交换按顺序排列
- 部分有序数组：数组中倒置的数量小于数组大小的某个倍数，包括以下情况：
- 数组中每个元素离排序后的最终位置不远；
- 一个有序的大数组连接一个乱序小数组的组合
- 数组中只有几个元素位置不正确
算法2.1
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。
