数据结构与算法-插入排序

什么是插入排序
插入排序是一种简单排序算法，一般适用于少量元素排序，其主要是将待排序元素插入已排序序列中以完成排序。

算法原理
1、定义初始元素为已排序序列
2、循环获取待排序元素与已排序序列元素比较，满足插入规则插入元素

时间复杂度
1、最好的情况已有序列，此时的时间复杂度为O(N)
2、最差的情况是完全乱序，此时的时间复杂度为O(N2)
综合时间复杂度为O(N2)

空间复杂度
算法局部变量不随被处理数据量n的大小而改变，故空间复杂度为O(1)

算法稳定性
由于待插入元素需要与已排序元素比较，不满足规则才进行插入，如果已排序序列存在相同元素是不会交换相互顺序的，故算法稳定。

小试牛刀
1、定义排序算法类，分别封装升序、降序

/**
 * 插入排序
 * @author senfel
 * @version 1.0
 * @date 2022/11/23 9:27
 */
@Slf4j
public class InsertionSort {

    /**
     * 插入排序>>升序
     * @param array
     * @author senfel
     * @date 2022/11/23 9:28
     * @return void
     */
    public static void sort(int[] array){
        if(null == array || array.length < 1){
            return;
        }
        log.error("插入排序>>升序,数组大小为：{}，预计排序次数为：{}",array.length,array.length-1);
        //默认第一位已有序列，从第二列开始执行插入算法
        for(int i = 1;i<array.length;i++){
            //缓存待排序元素
            int temp = array[i];
            //循环待排序数组,如果待排序元素小于已排序元素需要将已排序元素后移动，此时需要记录被移动元素索引
            //缓存移动索引
            int j = i;
            //为保证完全比较已排序序列需要 index > 0
            while (j>0 && array[j-1] > temp){
                //将该元素后移动
                array[j]=array[j-1];
                j--;
            }
            //如果待排序元素就是最大值此时待排序索引就是 j
            //如果不是最大值我们已经在上面算法将部分元素后移动,此时待排序索引也是j
            //直接插入元素
            array[j] = temp;
            log.error("第{}次排序,当前数组序列为：{}",i, Arrays.toString(array));
        }
        log.error("排序完成,数组最终序列为：{}", Arrays.toString(array));
    }

    /**
     * 插入排序>>降序
     * @param array
     * @author senfel
     * @date 2022/11/23 9:42
     * @return void
     */
    public static void inserted(int[] array){
        if(null == array || array.length < 1){
            return;
        }
        log.error("插入排序>>降序,数组大小为：{}，预计排序次数为：{}",array.length,array.length-1);
        //默认第一位已有序列，从第二列开始执行插入算法
        for(int i = 1;i<array.length;i++){
            //缓存待排序元素
            int temp = array[i];
            //循环待排序数组,如果待排序元素大于已排序元素需要将已排序元素后移动，此时需要记录被移动元素索引
            //缓存移动索引
            int j = i;
            //为保证完全比较已排序序列需要 index > 0
            while (j>0 && array[j-1] < temp){
                //将该元素后移动
                array[j]=array[j-1];
                j--;
            }
            //如果待排序元素就是最小值此时待排序索引就是 j
            //如果不是最小值我们已经在上面算法将部分元素后移动,此时待排序索引也是j
            //直接插入元素
            array[j] = temp;
            log.error("第{}次排序,当前数组序列为：{}",i, Arrays.toString(array));
        }
        log.error("排序完成,数组最终序列为：{}", Arrays.toString(array));
    }
}

2、测试插入排序算法

   public static void main(String[] args) {
        int[] array = {3,5,1,5,8,9,4,2};
        sort(array);
        int[] array2 = {3,5,1,5,8,9,4,2};
        inserted(array2);
    }

3、测试结果并展示步骤序列

09:45:58.652 插入排序>>升序,数组大小为：8，预计排序次数为：7
09:45:58.655 第1次排序,当前数组序列为：[3, 5, 1, 5, 8, 9, 4, 2]
09:45:58.655 第2次排序,当前数组序列为：[1, 3, 5, 5, 8, 9, 4, 2]
09:45:58.655 第3次排序,当前数组序列为：[1, 3, 5, 5, 8, 9, 4, 2]
09:45:58.655 第4次排序,当前数组序列为：[1, 3, 5, 5, 8, 9, 4, 2]
09:45:58.655 第5次排序,当前数组序列为：[1, 3, 5, 5, 8, 9, 4, 2]
09:45:58.655 第6次排序,当前数组序列为：[1, 3, 4, 5, 5, 8, 9, 2]
09:45:58.655 第7次排序,当前数组序列为：[1, 2, 3, 4, 5, 5, 8, 9]
09:45:58.655 排序完成,数组最终序列为：[1, 2, 3, 4, 5, 5, 8, 9]

09:45:58.655 插入排序>>降序,数组大小为：8，预计排序次数为：7
09:45:58.655 第1次排序,当前数组序列为：[5, 3, 1, 5, 8, 9, 4, 2]
09:45:58.656 第2次排序,当前数组序列为：[5, 3, 1, 5, 8, 9, 4, 2]
09:45:58.656 第3次排序,当前数组序列为：[5, 5, 3, 1, 8, 9, 4, 2]
09:45:58.656 第4次排序,当前数组序列为：[8, 5, 5, 3, 1, 9, 4, 2]
09:45:58.656 第5次排序,当前数组序列为：[9, 8, 5, 5, 3, 1, 4, 2]
09:45:58.656 第6次排序,当前数组序列为：[9, 8, 5, 5, 4, 3, 1, 2]
09:45:58.656 第7次排序,当前数组序列为：[9, 8, 5, 5, 4, 3, 2, 1]
09:45:58.656 排序完成,数组最终序列为：[9, 8, 5, 5, 4, 3, 2, 1]