算法--插入排序

1、概述

插入排序思想：对一个未排序的数组来说，将第一值当做已经被排好序的数组，然后从第二个值开始循环向前面排好序的数组进行比较插入。比较的顺序是从被排好序的数组的最后向前比较。

2、图解示例

观察可得：

1. 对数组排序需要进行 length - 1 轮遍历，并且将数组第一个值当做已经排好序的数组，从第二个值开始进行插入。
2. 每轮开始比较的位置为要插入的数据的下标 - 1。
3. 进行插入时：
   • 如果要插入的数据小于被比较的数据时，就将被比较的数据向后移一位，然后将被比较的下标 - 1，进行下轮的比较。
   • 如果下标 - 1已经超过了0，那说明要插入的数据为最小值，即插入到第一位。
   • 如果要插入的数据大于被比较的数据时，就将要插入的数据插入到被比较的数据后一位。

3、代码

package com.ld.algorithm.sort;

import java.util.Arrays;

/**
 * @author ld
 * @date 2020/8/8 22:38
 *
 * 算法--插入排序
 *
 * 对于一个未排序的数组来说，将第一值当做已经被排好序的数组，然后从第二个值开始循环向前面排好序的数组进行比较插入。
 * 比较的顺序是从被排好序的数组的最后向前比较。
 *
 */
public class InsertSort {

    public static void main(String[] args){

        //待排序的数组
        int[] array = {29,10,-3,90,3};

        System.out.println("排序前：" + Arrays.toString(array));

        //进行插入排序
        int[] sortArray = sort(array);

        //排好序的数组
        System.out.println("排序后：" + Arrays.toString(sortArray));
    }

    /**
     * 进行插入排序，从小到大排序
     * @param array 待排序的数组
     * @return 返回排序后的数组
     */
    public static int[] sort(int[] array){

        //将第一值当做已经被排好序的数组，然后从第二个值开始循环向前面排好序的数组进行插入
        for(int i = 1; i < array.length; i++){
            //要插入的数据
            int insertVal = array[i];
            //定义被插入的数组的结束位置，也是比较的开始位置。即要插入的数据下标减一
            int startIndex = i - 1;

            //循环判断当前被比较的下标有没有越界，并且判断插入的值是否小于要被比较的值，
            // 如果小于，就要将当前被比较的值向后移一位
            while(startIndex >= 0 && insertVal < array[startIndex]){
                array[startIndex + 1] = array[startIndex];
                //并且将被比较的下标向前移一位，进行下一轮的比较
                startIndex--;
            }

            //如果不满足上面的条件，
            //就表示插入的值大于被比较的值，所以要将插入的值插入到被比较的值后面。
            //或者前面已经没有数据，将值插入到最前面。
            array[startIndex + 1] = insertVal;
        }
        return array;
    }
}