- 算法可视化: 连接
- 时间复杂度，平均：\(O(n^2)\)，最坏：\(O(n^2)\)，最好：\(O(n)\)
- 空间复杂度，\(O(1)\)
- 是否稳定：稳定
- 本文图片来源：https://www.cnblogs.com/xiaoming0601/p/5862793.html
算法思想
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。 类似于扑克牌排序：
- 刚开始摸牌的时候左手是空的，接着一次从桌上摸一张牌，并将它插入到牌中的「正确」位置。
- 算法的核心步骤就是寻找「正确」位置。
- 手中的牌是有序的，然后摸起一张牌 M。
- 扫描手中的牌与 M 进行一一对比，找到插入的位置。
- 将 M 插入找到的位置即可。
- 为了提升效率，M 插入的时候牵涉到数组移动，所以可以一边对比一边移动，找到位置直接插入即可
/**
* 插入排序
*
* @author ychost
* @date 2018-4-3
*/
public class InsertSort {
void sort(int[] data) {
for (int i = 1; i < data.length; i++) {
int cur = data[i];
int j = i;
//找到插入位置
for (; j > 0; j--) {
//一边比较一边移位
if (cur < data[j - 1]) {
data[j] = data[j - 1];
} else {
break;
}
}
data[j] = cur;
}
}
}