排序系列
插入排序
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。
它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序在实现上，通常采用in-place排序（即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
算法步骤
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
-
从第一个元素开始，该元素可以认为已经被排序
-
取出下一个元素，在已经排序的元素序列中从后向前扫描
-
如果该元素（已排序）大于新元素，将该元素移到下一位置
-
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
-
将新元素插入到该位置后
-
重复步骤2~5
例子
和打扑克牌时类似，从牌桌上逐一拿起扑克牌，在手上排序的过程相同。
举例：
Input: {5 2 4 6 1 3}。
首先拿起第一张牌, 手上有 {5}。
拿起第二张牌 2, 把 2 insert 到手上的牌 {5}, 得到 {2 5}。
拿起第三张牌 4, 把 4 insert 到手上的牌 {2 5}, 得到 {2 4 5}。
以此类推。
java 实现
java 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39package com.github.houbb.sort.core.api;
import com.github.houbb.heaven.annotation.ThreadSafe;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import com.github.houbb.sort.core.util.InnerSortUtil;
import java.util.List;
/**
* 冒泡排序
* @author binbin.hou
* @since 0.0.5
*/
@ThreadSafe
public class InsertSort extends AbstractSort {
private static final Log log = LogFactory.getLog(InsertSort.class);
@Override
@SuppressWarnings("all")
public void doSort(List original) {
for(int i = 1; i < original.size(); i++) {
Comparable current = (Comparable) original.get(i);
int j = i-1;
// 从后向前遍历，把大于当前元素的信息全部向后移动。
while (j >= 0 && InnerSortUtil.gt(original, j, current)) {
// 元素向后移动一位
original.set(j+1, original.get(j));
j--;
}
// 将元素插入到对应的位置
original.set(j+1, current);
}
}
}
代码测试
1
2
3
4List<Integer> list = RandomUtil.randomList(10);
System.out.println("开始排序：" + list);
SortHelper.insert(list);
System.out.println("完成排序：" + list);
测试日志如下：
1
2开始排序：[31, 49, 86, 74, 64, 23, 12, 42, 93, 64]
完成排序：[12, 23, 31, 42, 49, 64, 64, 74, 86, 93]
开源地址
为了便于大家学习，上面的排序已经开源，开源地址：
欢迎大家 fork/star，鼓励一下作者~~
优化版本
v1-基础版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 /**
* 插入排序
* @param nums
* @return
*/
public static List<Integer> insertSort(int[] nums) {
List<Integer> resultList = new ArrayList<>(nums.length);
// 第一个元素。默认有序
resultList.add(nums[0]);
// 从数组中的第二个元素开始
for(int i = 1; i < nums.length; i++) {
// 从后向前遍历，把大于当前元素的信息全部向后移动。
int position = getInsertPosition(resultList, nums[i]);
resultList.add(position, nums[i]);
}
return resultList;
}
//O(n) 的插入寻找算法
private static int getInsertPosition(List<Integer> resultList, int target) {
for(int i = 0; i < resultList.size(); i++) {
int current = resultList.get(i);
if(target <= current) {
return i;
}
}
// 插入到最后
return resultList.size();
}
v2-binarySearch 版本
思路：我们把上面的 O(n) 查询，优化为 binary-search 算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14private static int getInsertPosition(List<Integer> resultList, int target) {
int left = 0;
int right = resultList.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (target <= resultList.get(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
// left 就是插入的索引位置
return left;
}
小结
堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)…1]逐步递减，近似为nlogn。
所以堆排序时间复杂度一般认为就是O(nlogn)级。
ps: 个人理解一般树的数据结构，时间复杂度都是 logn 级别的。
希望本文对你有帮助，如果有其他想法的话，也可以评论区和大家分享哦。
各位极客的点赞收藏转发，是老马持续写作的最大动力！
