排序—插入排序
许久没有写点东西了，答辩之后人也变得松懈。今天看到简书又有人点赞之前记录的冒泡排序，点进去一看，居然有4w+的阅读量，心生疑问，咋会有这么高的阅读量，打开百度搜索冒泡排序，结果第3条就是我的。点开认真看了看，其实写得不好，还改了两个错别字(狗头)，这个阅读量或许只是记录的点击量。但我萌生一个想法，趁现在有时间，想把排序系列做完，便于以后自己回顾。
排序系列传递门
排序—冒泡排序
排序—选择排序
排序—快速排序
排序-希尔排序（待完善）
排序—归并排序（待完善）
排序—基数排序（待完善）
排序—堆排序（待完善）
排序—桶排序（待完善）
排序—计数排序（待完善）
排序—排序算法总结（待完善）
插入排序思想
基本思想是在一个有序的序列中找到待排序元素的位置，比如将3插入-1，2，4，6这个有序序列中，先与6和4比较，直到和2比较之后，找到适合插入的位置(2之后)。
下面以按升序排序为例：
- step1 第一个元素默认有序。
- step2 取待排序的元素B，在有序序列上从后往前寻找。
- step3 如果已排序元素A大于待排序的元素B，则将A往后移动一位。
- step4 重复step3，直到找到元素A<=B(待排序)时或者有序序列全部被扫描。将待排序元素A插入。
- 重复step2—step4
动图展示(图片来源见参考资料)
代码实现(java)
/**
* 插入排序
* @param arr
*/
public static void insertSort(int[] arr) {
if(arr == null || arr.length == 0)
return;
int curEle, preIndex; // 记录当前待排序元素和前一个元素的下标
for(int i = 0; i < arr.length; i++) {
preIndex = i - 1;
curEle = arr[i];
while(preIndex >=0 && arr[preIndex] > curEle){
arr[preIndex + 1] = arr[preIndex]; // 移动元素
preIndex--;
}
// 将待排序元素插入新的位置
arr[preIndex + 1] = curEle;
}
}
算法分析
时间复杂度：$O(n^2)$
空间复杂度：$O(1)$
稳定性：稳定
参考资料
最后
本文若有不当，请指出。
此致，敬礼！
本文由博客一文多发平台 OpenWrite 发布！
版权声明：本文为numen-fan原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。