排序算法图解（三）：插入排序

深藏阁楼爱情的钟 2023-09-23 13:57 117阅读 0赞

### 文章目录 ###

*  1 插入排序简介
 *  2 插入排序思想及图解
 *  3 插入排序代码实现
 *  写在最后

--------------------

# 1 插入排序简介 #

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

--------------------

# 2 插入排序思想及图解 #

**插入排序的基本思想如下：**

把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为一个新的有序表。

以序列：`{55, 85, 21, 12, 5}` 为例， **图解如下：**

![在这里插入图片描述][3df688b0dc214b9383c892130f5fdcb3.png]  
粉红色部分为每轮认定的有序部分，其余颜色为认定的无序部分。绿色标识为每轮遍历的无序序列的位置，将该位置的元素逐一与有序部分进行比较，找到合适的位置进行顺序表的插入操作。

--------------------

# 3 插入排序代码实现 #

import java.util.Arrays;
    
    /**
     * @author 兴趣使然黄小黄
     * @version 1.0
     * 插入排序
     */
    public class InsertSort {
        
    
        public static void main(String[] args) {
        
            int[] array = {
        55, 85, 21, 12, 5};
            System.out.println("排序前: " + Arrays.toString(array));
            insertSort(array);
            System.out.println("排序后: " + Arrays.toString(array));
        }
    
        //插入排序
        public static void insertSort(int[] arr){
        
            //边界条件
            if (arr.length < 1){
        
                return;
            }
            for (int i = 1; i < arr.length; i++) {
        
                //定义待插入的位置和待插入的数
                int insertIndex = i-1; //arr[i]前面的位置,便于插入
                int insertVal = arr[i]; //先将待插入的值保存
                //给insertVal找到待插入的位置
                //1.insertIndex > 0防止越界
                //2.insertVal < arr[insertIndex] 说明还未找到待插入的位置
                while (insertIndex >= 0 && insertVal < arr[insertIndex]){
        
                    arr[insertIndex+1] = arr[insertIndex];
                    insertIndex--;
                }
                if (insertIndex != i){
        
                    arr[insertIndex+1] = insertVal; //插入
                }
                System.out.println("第" + i + "轮: " + Arrays.toString(arr));
            }
        }
    }

**结果如下：**  
![在这里插入图片描述][d279a7b348c14d1dbb4915ea82b43727.png]

--------------------

# 写在最后 #

**本文被 [Java数据结构][Java] 收录[点击订阅专栏][Java]** ， 持续更新中。  
 创作不易，如果你有任何问题，欢迎私信，感谢您的支持！

![在这里插入图片描述][7e0ff0501697426a84cd0a1f4eecfdc1.gif_pic_center]

[6a6b359934b74fbdbc2b9d1e67819296.png]: https://img-blog.csdnimg.cn/6a6b359934b74fbdbc2b9d1e67819296.png
[3df688b0dc214b9383c892130f5fdcb3.png]: https://img-blog.csdnimg.cn/3df688b0dc214b9383c892130f5fdcb3.png
[d279a7b348c14d1dbb4915ea82b43727.png]: https://img-blog.csdnimg.cn/d279a7b348c14d1dbb4915ea82b43727.png
[Java]: https://blog.csdn.net/m0_60353039/category_12062687.html
[7e0ff0501697426a84cd0a1f4eecfdc1.gif_pic_center]: https://img-blog.csdnimg.cn/7e0ff0501697426a84cd0a1f4eecfdc1.gif#pic_center