插入排序

基本思想
直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。简单插入排序在最好情况下，需要比较n-1次，无需交换元素，时间复杂度为O(n);在最坏情况下，时间复杂度依然为O(n2)。但是在数组元素随机排列的情况下，插入排序还是要优于上面两种排序的。插入排序的过程如下：
Java实现

/**
     * 插入排序
     *
     * @param arr
     */
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            while (j > 0 && arr[j] < arr[j - 1]) {
                swap(arr,j,j-1);
                j--;
            }
        }
    }

链表的插入排序

题目：Sort a linked list using insertion sort.
链表的插入排序涉及一些指针的处理技巧需要注意。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if(head == NULL || head->next == NULL)
            return head;
        ListNode *dumy = new ListNode(INT_MIN); //创建一个哑结点对下面的过程有很大的方便
        ListNode *cur = head;
        ListNode *dcur = dumy;
        while(cur != NULL){
            ListNode * next = cur->next; //保存当前节点的下一节点
            dcur = dumy;
            while(dcur->next != NULL && dcur->next->val < cur->val){
                dcur = dcur->next;
            }
            cur->next = dcur->next; //指针的处理需要注意
            dcur->next = cur;
            cur = next;
        }
        return dumy->next;
    }
};

参考文章: 图解排序算法(一)之3种简单排序(选择，冒泡，直接插入)