插入排序之直接插入

原理：将数组分为无序区和有序区两个区，然后不断将无序区的第一个元素按大小顺序插入到有序区中去，最终将所有无序区元素都移动到有序区完成排序。
要点：设立哨兵，作为临时存储和判断数组边界之用。

    private static void sortInsert(int[] array) {
        //逐步扩大有序区
        for (int i = 1; i < array.length; i++) {
            int key = array[i];
            //分别为无序区i和有序区j指针
            int j = i - 1;
            //寻找插入位置
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            //插入元素
            array[j + 1] = key;
            printArray(String.format(Locale.getDefault(), "key = %2d , j = %2d : ", key, j + 1), array);
        }
    }

运行结果：

数组：  55  22  66  33  11  99  77  44  88
插入排序：
key = 22 , j =  0 :   22  55  66  33  11  99  77  44  88
key = 66 , j =  2 :   22  55  66  33  11  99  77  44  88
key = 33 , j =  1 :   22  33  55  66  11  99  77  44  88
key = 11 , j =  0 :   11  22  33  55  66  99  77  44  88
key = 99 , j =  5 :   11  22  33  55  66  99  77  44  88
key = 77 , j =  5 :   11  22  33  55  66  77  99  44  88
key = 44 , j =  3 :   11  22  33  44  55  66  77  99  88
key = 88 , j =  7 :   11  22  33  44  55  66  77  88  99