LowB三人组--插入排序原理和java实现

简介: LowB三人组--插入排序原理和java实现


插入排序原理图

https://www.runoob.com/w3cnote/insertion-sort.html

java实现代码

/**
 * 插入排序
 */
public class InsertionSortTest {
    public static void main(String[] args) {
        int[] arr = {2,4,7,5,3,6,8,9,1};
        insertionSort(arr);
    }
    /**
     * 插入排序的原理:
     * 将待排序数组看成两部分: 有序数组和无序数组,初始时,第一次可以将第一张看成有序数组,其余作为无序数组
     *  无序数组插入到有序数组中,遍历无序数组(无序数组个数就是需要插入的次数)
     *      将有序数组的右侧第一张和 无序的第一张,
     *         如果 从有序的右侧起: 获取无序的元素小于于有序的元素的第一个元素的索引,有序的这些元素向右移动一位
     *                           同时当前的索引值+1的位置就是 插入的元素
     */
    public static void insertionSort(int[] arr){
        //外层为 要插入的元素
        for (int i=1;i<arr.length;i++){
            //有序位置的最后一个元素
            int tmp = arr[i];
            //获取要插入的元素的位置
            int j = i - 1;
            //从右侧起,获取第一个比要插入的元素小的元素的索引,索引右侧的值 右移一位
            while (j>=0 && arr[j]  > tmp){
                arr[j+1] = arr[j];
                //arr[j] = tmp;
                j--;
            }
            arr[j+1] = tmp;
            System.out.println(Arrays.toString(arr));
        }
    }
}

运行结果:

复杂度


相关文章
|
1天前
|
Java
Java之CountDownLatch原理浅析
本文介绍了Java并发工具类`CountDownLatch`的使用方法、原理及其与`Thread.join()`的区别。`CountDownLatch`通过构造函数接收一个整数参数作为计数器,调用`countDown`方法减少计数,`await`方法会阻塞当前线程,直到计数为零。文章还详细解析了其内部机制,包括初始化、`countDown`和`await`方法的工作原理,并给出了一个游戏加载场景的示例代码。
Java之CountDownLatch原理浅析
|
3天前
|
Java 索引 容器
Java ArrayList扩容的原理
Java 的 `ArrayList` 是基于数组实现的动态集合。初始时,`ArrayList` 底层创建一个空数组 `elementData`,并设置 `size` 为 0。当首次添加元素时,会调用 `grow` 方法将数组扩容至默认容量 10。之后每次添加元素时,如果当前数组已满,则会再次调用 `grow` 方法进行扩容。扩容规则为:首次扩容至 10,后续扩容至原数组长度的 1.5 倍或根据实际需求扩容。例如,当需要一次性添加 100 个元素时,会直接扩容至 110 而不是 15。
Java ArrayList扩容的原理
|
1天前
|
存储 算法 Java
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
本文详解自旋锁的概念、优缺点、使用场景及Java实现。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
|
9天前
|
存储 Java 关系型数据库
在Java开发中,数据库连接是应用与数据交互的关键环节。本文通过案例分析,深入探讨Java连接池的原理与最佳实践
在Java开发中,数据库连接是应用与数据交互的关键环节。本文通过案例分析,深入探讨Java连接池的原理与最佳实践,包括连接创建、分配、复用和释放等操作,并通过电商应用实例展示了如何选择合适的连接池库(如HikariCP)和配置参数,实现高效、稳定的数据库连接管理。
24 2
|
9天前
|
算法 Java 数据库连接
Java连接池技术,从基础概念出发,解析了连接池的工作原理及其重要性
本文详细介绍了Java连接池技术,从基础概念出发,解析了连接池的工作原理及其重要性。连接池通过复用数据库连接,显著提升了应用的性能和稳定性。文章还展示了使用HikariCP连接池的示例代码,帮助读者更好地理解和应用这一技术。
23 1
|
搜索推荐 Java
希尔排序(简单易懂,图文并貌,插入排序)java代码实现
希尔排序(简单易懂,图文并貌,插入排序)java代码实现
151 0
希尔排序(简单易懂,图文并貌,插入排序)java代码实现
|
搜索推荐 算法 Java
插入排序(直接插入排序)java代码实现(注释详细 简单易懂)
插入排序(直接插入排序)java代码实现(注释详细 简单易懂)
131 0
|
Java 机器学习/深度学习 Shell
|
10天前
|
安全 Java
java 中 i++ 到底是否线程安全?
本文通过实例探讨了 `i++` 在多线程环境下的线程安全性问题。首先,使用 100 个线程分别执行 10000 次 `i++` 操作,发现最终结果小于预期的 1000000,证明 `i++` 是线程不安全的。接着,介绍了两种解决方法:使用 `synchronized` 关键字加锁和使用 `AtomicInteger` 类。其中,`AtomicInteger` 通过 `CAS` 操作实现了高效的线程安全。最后,通过分析字节码和源码,解释了 `i++` 为何线程不安全以及 `AtomicInteger` 如何保证线程安全。
java 中 i++ 到底是否线程安全?
|
1天前
|
安全 Java 测试技术
Java并行流陷阱:为什么指定线程池可能是个坏主意
本文探讨了Java并行流的使用陷阱,尤其是指定线程池的问题。文章分析了并行流的设计思想,指出了指定线程池的弊端,并提供了使用CompletableFuture等替代方案。同时,介绍了Parallel Collector库在处理阻塞任务时的优势和特点。