Java【直接插入排序】算法, 大白话式详细图文解析(附代码)-Toy模板网

这篇具有很好参考价值的文章主要介绍了Java【直接插入排序】算法, 大白话式详细图文解析(附代码)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

📕各位读者好, 我是小陈, 这是我的个人主页
📗小陈还在持续努力学习编程, 努力通过博客输出所学知识
📘如果本篇对你有帮助, 烦请点赞关注支持一波, 感激不尽
📙 希望我的专栏能够帮助到你:
JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等
Java数据结构: 顺序表, 链表, 堆, 二叉树, 二叉搜索树, 哈希表等
JavaEE初阶: 多线程, 网络编程, TCP/IP协议, HTTP协议, Tomcat, Servlet, Linux, JVM等(正在持续更新)

本篇继续分享七大排序算法中的 直接插入排序 , 其余六个算法也有介绍噢
想看哪个点哪个 : 选择排序, 希尔排序, 堆排序, 冒泡排序, 快速排序, 归并排序

提示：是正在努力进步的小菜鸟一只，如有大佬发现文章欠佳之处欢迎评论区指点~ 废话不多说，直接发车~

一、排序相关概念

1, 什么是排序

📌排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增📈或递减📉的排列起来的操作

👉以 int 类型数据从小到大排序为例：
排序前：4，1，3，6，8，7，2，5
排序后：1，2，3，4，5，6，7，8

2, 什么是排序的稳定性

📌稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

👉以 int 类型数据从小到大排序为例：
排序前：4，1，3a，6，8，7，2，3b，5（3a 在 3b 之前）
排序后：1，2，3a，3b，4，5，6，7，8（3a 还在 3b 之前，稳定）
排序后：1，2，3b，3a，4，5，6，7，8（3a 不在 3b 之前，不稳定）

3, 七大排序分类

以下是常见的 7大排序 算法
Java【直接插入排序】算法, 大白话式详细图文解析(附代码)

二、直接插入排序

1, 图文解析

📌直接插入排序的基本操作是将一个记录插入到已经排有序的有序表中, 从而得到一个新的有序表

📌基本思想 : 类似于打扑克牌, 比如你现在手上有三张牌:3, 5, 10, 现在轮到你摸牌了, 你摸了一张7, 你应该把7放在哪里呢?

对于手上已有的3, 5, 10来说这几张牌已经排好序了, 那么把 7 插在那里还能保持有序呢? 很简单, 就在 5 和 10 的中间

🚗🚗🚗
那么给定一组无序的数据, 实现直接插入排序的具体过程是什么呢? 如图所示
注意 i , j 下标的变化 Java【直接插入排序】算法, 大白话式详细图文解析(附代码)

2, 代码实现

为了方便在 Test 类中测试, 把所有的方法设置为 static 修饰的静态方法

    /**
     * 直接插入排序
     * 时间复杂度：最坏 O（N^2），最好 O（N）
     * 空间复杂度：O（1）
     * 稳定性：稳定
     * @param array ：待排序数组趋于有序时，使用插入排序效率高
     */
    public static void insertSort(int[] array) {
        // 从小到大排序
        if(array == null) {
            return;
        }
        int tmp = 0;
        for (int i = 1; i < array.length; i++) {
            tmp = array[i];
            for (int j = i - 1; j >= 0; j--) {
                // j往前走
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                    array[j] = tmp;
                } else {
                    break;
                }
            }
        }
    }