基本排序算法 - 插入排序

排序算法相关理论网上资料已经很多了，这里记录一下代码方便复习。

插入排序核心思想：
把数组分为有序表和无序表，从后面无序表中依次取出第一个数，插入到有序表的适当位置。

/**
 * @Description: 插入排序
 *
 * 1.从第一个元素开始，该元素可以认为已经被排序
 * 2.取出下一个元素，在已经排序的元素序列中从后向前扫描
 * 3.如果该元素（已排序）大于新元素，将该元素移到下一位置
 * 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
 * 5.将新元素插入到该位置后
 * 6.重复步骤2~5
 */
public class InsertSort {

    public static void main(String[] args) {

        int[] arr = {5, 2, 9, 6, 10, 21, 16};
        int len = arr.length;

        int insertVal = 0;
        int insertIndex = 0;

        for (int i = 1; i < len; i++) {
            // 待插入的数
            insertVal = arr[i];
            // arr[i]前一个数的下标
            insertIndex = i - 1;

            /**
             * 为insertVal找插入位置
             * 1. insertIndex >= 0 保证下标不越界
             * 2. insertVal < arr[insertIndex]待插入的数，说明还未找到插入位置
             * 3. 将arr[insertIndex]后移一个位置（赋值给后一个位置），覆盖后面的数。
             *    如第一轮时为[5, 5, 9, 6, 10, 21, 16]，找到插入位置0后将insertVal=2赋值给arr[0]覆盖原有的5
             */
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }

            // 退出while循环时说明插入位置找到
            // 因为退出while循环前多执行了一次insertIndex--，所以 insertIndex + 1 才是要插入的位置
            if (insertIndex + 1 != i) {
                arr[insertIndex + 1] = insertVal;
            }

            System.out.println("第"+i+"轮："+Arrays.toString(arr));

        }
        System.out.println(Arrays.toString(arr));
    }

}

打印结果：

第1轮：[2, 5, 9, 6, 10, 21, 16]
第2轮：[2, 5, 9, 6, 10, 21, 16]
第3轮：[2, 5, 6, 9, 10, 21, 16]
第4轮：[2, 5, 6, 9, 10, 21, 16]
第5轮：[2, 5, 6, 9, 10, 21, 16]
第6轮：[2, 5, 6, 9, 10, 16, 21]
[2, 5, 6, 9, 10, 16, 21]