思路：先将当前值保存到value中，遍历之前的所有元素并且与其比较，如果num大于value，则将num往后移动一位覆盖value并继续比较前一个，直到value之前的某个值小于等于value时，结束遍历，并将value值赋给该值得后一个位置。从描述看出，插入排序是稳定的。
估计不好理解，看图说话：
具体代码：
1 public static void insertSort(int[] nums) {
2 int insertValue = 0;
3 int insertIndex = 0;
4 boolean flag=false;
5 for (int i = 1; i < nums.length; i++) {
6 insertValue = nums[i];// 保存当前需要插入到有序表的数值
7 insertIndex = i - 1;// 表示要与当前数值进行比较的值的下标
8 for (int j = insertIndex; j >= 0; j--) {// 在当前值的前面的有序表中遍历
9 if (nums[insertIndex] > insertValue) {// 如果待插入的值小于有序表中的某值(从后往前)
10 nums[insertIndex + 1] = nums[insertIndex];// 那么就将某值后移
11 insertIndex--;// 这里用于记录要插入的位置
12 }
13 }
14
15 nums[insertIndex + 1] = insertValue;// 因为真正的待插入的位置在遍历完是在待插入位置的前一个，所以要将待插入位置+1
16 }
17 }
测试：
插入排序的最坏情况下：时间复杂度为O(n2)；最好情况下O(n) 空间复杂度：O(1)
测试80000随机数，范围在1000w内的随机数。结果如下：
前后差约为：5秒（同条件下相比冒泡提升了3倍以上的效率）
before: 23:18:04:379
after: 23:18:09:187
1 public static void insertSort(Node head) {
2 if (null == head.getNext()) {
3 return;
4 }
5 Node temp = head.getNext();
6 while (temp != head) {
7 temp = temp.getNext();
8 if (temp == head)
9 break;
10 int insertValue = temp.getValue();
11 Node insertPointer = temp.getPre();
12 while (head != insertPointer) {
13 if (insertPointer.getValue() > insertValue && insertPointer.getPre().getValue() <= insertValue) {
14 insertPointer = insertPointer.getPre();
15
16 temp.getPre().setNext(temp.getNext());
17 temp.getNext().setPre(temp.getPre());
18
19 Node insertNode = new Node(insertValue);
20 insertNode.setNext(insertPointer.getNext());
21 insertPointer.getNext().setPre(insertNode);
22 insertPointer.setNext(insertNode);
23 insertNode.setPre(insertPointer);
24
25 continue;
26 }
27 insertPointer = insertPointer.getPre();
28 }
29 }
30 }
可能自己书写不当，不推荐链表排序，同样80000个数，居然要1分钟才排好。。。看看就行了。学习链表其中的技巧。
原文：https://www.cnblogs.com/taichiman/p/13268971.html