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

港控/mmm° 2024-03-31 10:21 65阅读 0赞

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

**算法原理**  
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\]