《算法》学习笔记2.1 初级排序算法
2.1 初级排序算法
- 2.1.1 选择排序
- 2.1.2 插入排序
- 2.1.3 选择、插入排序比较
- 2.1.4 希尔排序
- 2.1.5 其他
- 数据类型
- 几种典型的部分有序数组
- 插入排序中的哨兵
2.1.1 选择排序
1.思想
不断地选择剩余元素之中的最小者
2.1.2 插入排序
1.思想
插入已经有序的数组中的适当位置，其余元素在插入之前都向右移一位
2.最优适用情况
- 部分有序的数组；
- 小规模数组
2.1.3 选择、插入排序比较
| 测试数组 | 比较/次数 | 交换/次数 | |
|---|---|---|---|
| 选择排序 | 长度为N | N2/2 | N |
| 插入排序 | 长度为N且主键不重复 | 最坏：N2/2 最好：N2/2 | 最坏：N-1 最好：0 |
比较两种排序算法：sortCompare()
2.1.4 希尔排序
1.思想
使数组中任意间隔为h的元素有序的
2.最优适用情况
- 中等大小的数组；
- 需要解决一个排序问题而又没有系统排序函数可用，可先用希尔，再考虑是否值得用其他替代
2.1.5 其他
数据类型
实现Comparable()接口
几种典型的部分有序数组
- 数组中的每个元素距离他的最终位置都不远
- 一个有序的大数组接一个小数组
- 数组中只有几个元素的位置不正确
插入排序中的哨兵
插入排序的实现中先找出最小的元素将其置于数组的最左边，这样就能去掉内循环的判断条件j>o，这是一种常见的规避边界测试的方法，能够省略判断条件的元素通常被称为哨兵
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！