public class InsertSorts {
    static public void insertSort0(int[] sourceArray) {
        int arrayLength = sourceArray.length;
        //把第一个元素看成是已经有序的序列。
        //把从第二个开始的元素陆续插入到这个有序序列中
        //然后使之仍然有序。
        for (int counter = 1;counter < arrayLength;counter++) {
            //外层循环用于挑选即将被插入到已经有序的序列中的元素。
            //这个要被插入的元素是从第二个开始的，直到最后。
            //接下来是比较即将被插入的元素和已经有序的序列中的元素
            //现在我要从大到小排序
            //那说明已经有序的序列就是从大到小的顺序了
            //所以我只需要把这个待插入元素从前往后比较，只要碰到后面的元素比它小，
            //那么这个位置就是它要被插入的位置了。
            //先取出待插入的元素。
            int elementToBeInserted = sourceArray[counter];
            for (int counter0 = 0;counter0 < counter;counter0++) {
                if (elementToBeInserted > sourceArray[counter0]) {
                    //此时代表已经找到了插入位置
                    for (int counter1 = counter;counter1 > counter0;counter1--) {
                        //依次挪动数组元素往后
                        sourceArray[counter1] = sourceArray[counter1-1];
                    }
                    //插入
                    sourceArray[counter0] = elementToBeInserted;
                    //结束子循环
                    break;
                } else continue;
            }
        }
    }

    /**
     * 这个版本的插入排序法更加精简
     * @param sourceArray
     */
    static public void insertSort1(int[] sourceArray) {
        int arrayLength = sourceArray.length;
        for (int counter = 1;counter < arrayLength;counter++) {
            int tempElement = sourceArray[counter];
            int previousPointer = counter - 1;
            while (previousPointer >= 0 && tempElement > sourceArray[previousPointer]) {
                //挪动位置
                sourceArray[previousPointer + 1] = sourceArray[previousPointer];
                //从前往后遍历会多一个临时变量
                previousPointer--;
            }
            sourceArray[++previousPointer] = tempElement;
        }
    }
}