排序算法 --- 插入排序
之气说到了冒泡和选择排序，接下来看看插入排序。
一、排序思想
把n个待排的元素看成一个有序表和一个无序表，开始时，有序表只包含1个元素，无序表中有n - 1个元素。排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码比较，将它插入适当的位置，使之成为新的有序表。
欢迎大家关注我的公众号 javawebkf，目前正在慢慢地将简书文章搬到公众号，以后简书和公众号文章将同步更新，且简书上的付费文章在公众号上将免费。
1. 案例：
假如现有待排序列如下(带 * 号的是有序表元素)：
17* 3 25 14 20 9那么开始的时候，17就是有序表，剩余元素是一个无序表。
- 第一次：让3和有序表最后一个元素17比较，发现3比17小，那么就让17往后挪一位，然后让3再和前面的比较，发现前面没有元素了，所以第一次排序后的结果是：
3* 17* 25 14 20 9- 第二次：让25和17比较，发现25比17大，那么就不用变换位置，第二次排序后的结果是：
3* 17* 25* 14 20 9- 第三次：让14和有序表元素比较，结果是：
3* 14* 17* 25* 20 9- 第四次：让20和有序表元素比较，结果是：
3* 14* 17* 20* 25* 9- 第五次：让9和有序表元素比较，结果是：
3* 9* 14* 17* 20* 25*二、代码实现
代码中有详细的注释：
public static void sort(int[] arr) {
if (arr == null || arr.length == 1) {
return;
}
for(int i=1; i<arr.length; i++) { // 默认第一个是有序表，从第二个元素开始进行插入排序
int insertVal = arr[i]; // 待排元素
int insertIndex = i - 1; // 从有序表最后一个元素开始比较
while (insertIndex >= 0 && insertVal < arr[insertIndex]) { // 如果还没有将有序表比较完 && 待排元素还没找到位置
arr[insertIndex + 1] = arr[insertIndex]; // 比待排元素大的元素后移一位
insertIndex --; // 继续往前比较
}
// 找到位置后，其他元素都后移了，自己占坑
if (insertIndex + 1 != i) {
arr[insertIndex + 1] = insertVal;
}
}
}三、存在的问题
假如现在有如下序列：
16, 23, 12, 8, 1要求按照从小到大的顺序排列，你会发现，最小的1在最后面，第二小的8在倒数第二个位置，那么在排序的时候，就会发生很多次交换，即while循环里面的代码会执行很多次，1在排序的时候就会执行四次，这样性能就下降了。有没有优化的空间呢？有，那就是希尔排序……
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录