【算法排序】直接插入排序详解与实现

朴灿烈づ我的快乐病毒、 2023-10-11 22:04 49阅读 0赞

#### 目录 ####

*  一、前言
 *  二、概念及其介绍
 *  三、过程图示
 *  四、复杂度以及稳定性
 *   *  1、时间复杂度
     *  2、空间复杂度
 *  五、代码实现
 *  六、算法过程
 *  七、使用场景和注意事项
 *  八、总结

## 一、前言 ##

在计算机科学中，排序算法是一项基本且重要的任务，用于将一组元素按照特定顺序排列。直接插入排序是最简单的排序算法之一，尽管其效率相对较低，但对于小规模数据或基本有序的数据集合，它仍然是一个重要且有趣的算法。本文将深入探讨直接插入排序的原理、步骤以及实现方式

## 二、概念及其介绍 ##

插入排序(InsertionSort)，一般也被称为直接插入排序。  
对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表。  
在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

## 三、过程图示 ##

假设前面 n-1(其中 n>=2)个数已经是排好顺序的，现将第 n 个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。  
按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。  
从小到大的插入排序整个过程如图示：  
**第一轮：** 从第二位置的 6 开始比较，比前面 7 小，交换位置。  
![在这里插入图片描述][1bf2b82a9d8b47ddb6c7876dc6434447.png]  
**第二轮：** 第三位置的 9 比前一位置的 7 大，无需交换位置  
![在这里插入图片描述][548d3283576c4e64b061f11cbc56f560.png]  
**第三轮：** 第四位置的 3 比前一位置的 9 小交换位置，依次往前比较。  
![在这里插入图片描述][a07f13f32f14451db1a5da26e2592d10.png]  
**第四轮：** 第五位置的 1 比前一位置的 9 小，交换位置，再依次往前比较。  
![在这里插入图片描述][04ccd5565d8140858e02a16c4a2d2750.png]

## 四、复杂度以及稳定性 ##

### 1、时间复杂度 ###

首先直接插入排序是一个稳定的排序算法，**最好的情况下**：也就是排序本身是有序的，共需比较n-1次，因为没有移动的记录，时间复杂度为O(n)；**最坏的情况下**：即排序表是逆序的情况，时间复杂度为O(n²)

### 2、空间复杂度 ###

算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数。在直接插入排序中只使用了i,j,temp这三个**辅助空间单元**，所以空间复杂度是O(1)。

## 五、代码实现 ##

public class StraightInsertionSort {
        
        public static void main(String[] args){
        
            //定义一个待排元素数组
            Integer[] arr = {
        5,2,7,3,9,10,8,6,1,4};
            insertSort(arr);
            System.out.println("最终排序结果为"+Arrays.toString(arr));
        }
    
        //假设从小到大排序
        public static void insertSort(Integer[] arr){
        
            //寻找元素arr[i]合适的插入位置，i是当前元素
            for (int i = 1; i < arr.length; i++) {
        
                //记录待排元素的值
                int temp = arr[i];
                int position = i;
                //j是从i-1开始向前移动的，并且每次与arr[i]判断大小
                for (int j = i-1; j >= 0 ; j--) {
        
                    //如果temp小于arr[j]，就说明temp当前至少要插入到arr[j]的前面
                    if(temp < arr[j]){
        
                        //记录后移
                        arr[j+1] = arr[j];
                        position = j;
                    }else {
        
                        break;
                    }
                }
                //插入到正确位置
                arr[position]=temp;
                //输出每一步排序的结果
                System.out.println("第"+i+"轮排序结果为"+Arrays.toString(arr));
            }
        }
    }

## 六、算法过程 ##

> 整个算法过程分为以下几步：

1）每次从无序表中取出第一个元素，把它插入到有序表的**合适**位置，使有序表仍然有序。  
2）第一趟比较前两个数，然后把第二个数按大小**插入**到有序表中。  
3）第二趟把第三个数据与前两个数从后向前**比较**，把第三个数按大小插入到有序表中。  
4）依次进行下去，进行了(n-1)趟比较以后就完成了整个**排序**过程。

## 七、使用场景和注意事项 ##

1.  直接插入排序适用于小规模数据集或基本有序的数据。
2.  在数据量较大或要求更高性能的情况下，可能会考虑其他更优的排序算法，如快速排序或归并排序。

## 八、总结 ##

直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。

[1bf2b82a9d8b47ddb6c7876dc6434447.png]: https://img-blog.csdnimg.cn/1bf2b82a9d8b47ddb6c7876dc6434447.png
[548d3283576c4e64b061f11cbc56f560.png]: https://img-blog.csdnimg.cn/548d3283576c4e64b061f11cbc56f560.png
[a07f13f32f14451db1a5da26e2592d10.png]: https://img-blog.csdnimg.cn/a07f13f32f14451db1a5da26e2592d10.png
[04ccd5565d8140858e02a16c4a2d2750.png]: https://img-blog.csdnimg.cn/04ccd5565d8140858e02a16c4a2d2750.png