參考別人的文章記錄下來，方便自己查看

插入排序是一種最簡單直觀的排序算法，它的工作原理是通過構建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應位置并插入。

算法步驟：

將待排序序列的<code>第一個元素</code>看做一個<code>有序序列</code>，把第二個元素到最后一個元素當成是<code>未排序序列</code>。

從頭到尾依次掃描<code>未排序序列</code>，將掃描到的每個元素插入有序序列的適當位置。（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面。）

    /**
     * 插入排序
     * @param a
     */
    public static void insertSort(int[] a) {
        //第一個元素作為有序序列；剩下的第二個元素到末尾元素為無序序列
        //從第二個元素掃描序列
        for(int i=1; i<a.length; i++) {
            int target = a[i]; //此次需移動的目標
            int j = i; //j是最終target移動到的位置
            //target與有序序列比較，找到適合的位置j；同時將比target大的
            while(j>0 && target < a[j-1]) {
                a[j] = a[j-1]; //比target大的有序序列數(shù)據(jù)右移
                j--; //target小于有序序列的數(shù)據(jù)時，j左移
            }
            //插入 
            a[j] = target; //在位置j上賦值target
        }
    }