数据结构——插入排序（算法）

基本介绍：

• 插入排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以到达排序的目的

基本思想：

• 把N个待排序的元素看成为一个有序表和无序表，开始时，有序表中只包含一个元素，无序表中包含N-1个元素 ， 排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
  

示例代码

    private static void insertSortAsc(int[] array) {
        /*用于记录当前即将要插入的值*/
        int tempValue;
        /*用于记录当前索引位置的前一个索引*/
        int beforeIndex;
        /*默认第一个位置索引0的数据是有序的，从第二个位置的数据开始循环，直到最后一个位置的元素*/
        for (int i = 1; i < array.length; i++) {
            tempValue = array[i];
            beforeIndex = i;
            /*以下两个条件与关系*/
            /*1、若beforeIndex = 0：说明当前位置已第一个位置，即为当前元素应在位置*/
            /*2、升序：tempValue < array[beforeIndex]，如果当前小于前一个位置的元素*/
            /*2、降序：tempValue > array[beforeIndex]，如果当前大于前一个位置的元素*/
            /*如果条件存在，说明还未为当前元素找到正确位置*/
            while (beforeIndex > 0 && tempValue < array[beforeIndex - 1]) {
                /*将有序元素进行位置挪动*/
                array[beforeIndex] = array[beforeIndex - 1];
                /*指针移动，进行元素循环，对前一个位置元素进行判断*/
                beforeIndex--;
            }
            /*循环完毕，找到元素位置,将当前值赋给所找到位置*/
            array[beforeIndex] = tempValue;
        }
    }