插入排序的思想跟选择排序类似，都是从后面选择元素往前面“放”，导致这两种算法经常”傻傻分不清楚”。笔者认为它们两个最大的区别已经体现在“放”的策略上。
假设现有无序数组A0到A5处在，它们分别对应着数组中的0到5号位。要求实现从小到大排列。
所谓的选择排序，它侧重从A0到A5中选出最小的一个元素，放到0号位上；然后在剩余元素中选出次小元素，放在1号位上，依次类推…
而插入排序，它里面引入了分组的概念，核心是把数组分为有序和无序的两部分，然后将无序的元素依次插入到有序序列中。先将数组分成A0、A1-A5两部分，A0是有序的（为啥，一个元素还不有序，你想上天），将A1与A0比较，如果A0比A1大，则将A0移到1号位，A1放到0号位；如果A0比A1小，则什么也不做。此时A0和A1就是有序序列，然后需要找出A2在这个有序序列中的位置（有序序列从后往前取出元素与A2比较），将其插入进去即可。
形象一点说像极了平时大家钟爱的打牌运动。笔者寂寞的喜欢一个人斗地主（这爱好…），运气一直很衰，MD第一张是个3！！！没办法，拿出来放到最左边，此时手里的牌是有序的，桌面的牌就是无序的部分。再摸一张，我擦是个5，笔者有强迫症，必须放到3后面。再摸一张傻眼了，竟然是个4，那5往后挪，4放到5原来的位置上吧…直到排好王炸，哈哈，又赢了5000金豆（…）
条件： 数据基本有序时，选择排序是一种很高效的算法。JDK1.8中排序算法的实现，当数据量小于47时，选择的就是插入排序，在这个数量级上，选择排序的性能是优于快排的。
原理： （1）分组有序和无序的； （2）将无序的依次插入到有序的当中； ….
时间复杂度：
同样没什么好说的，n^2。
笔面试出现的频率：
除了在线笔试偶尔有几个脑残题，面试和现场笔试从来没有考过。
实现：
public class InsSort { /** * <p>name: main</p> * <p>description: </p> * <p>return: void</p> */ public static void main(String[] args) { int[] a = { 1, 5, 8, 4, 7, 3, 0, 2, 9, 6, 11, 13, 12, 141, 14, 15, 17, 16, 18, 21, 20, 19, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 40, 39, 38, 37 }; insSort(a); print(a); } public static void print(int[] array) { for (int i = 0; i < array.length; i++) { System.out.print(array[i] + ", "); } System.out.println(); } /** 取出当前元素，往前查找空缺，分块容易遗忘，多写 */ public static void insSort(int[] array) { for (int i = 1; i < array.length; i++) { int ins = array[i];// 取出当前元素 int j = i - 1;// 往前查找空缺 while (j >= 0 && array[j] > ins) { array[j + 1] = array[j]; j--; } array[j + 1] = ins; } } }