【算法】插入排序算法原理及实现

简介: 【算法】插入排序算法原理及实现

1.什么是插入排序

  • 每一步将一个待排序的数据插入到前面已经排序好的有序序列里,直到插完所有的元素为止。
  • 插入排序与打扑克牌很类似,你摸到第一张牌的时候是不需要排序的,后续摸到的牌可以根据第一张牌进行向左或者向右排序。
  • 算法实现
  • 直接插入排序是把无序的序列里的数据插入到有序的序列中去。
  • 在遍历无序序列的时候,首先拿无序序列里的第一个元素跟有序序列里的每一个元素比较,并且插入到合适的位置,一直到无序序列里的所有元素插入完毕为止。

2.插入排序算法图解

  • 初始化序列如下所示,分为有序序列(没有任何元素)和无序序列(8,2,6,4,3,7,5),一开始有序序列是没有任何元素的。


37b18e351d5545a18778d4f2bdcbd1ab.jpg

第一轮用8和2比较,返现2比8小,交换位置,变成2 8

第二轮用8和6比较,交换位置,然后再用2和6比较,发现6比2大不用交换位置变成 2 6 8

第三轮用8和4比较,交换位置,再用6和4比较交换位置,2和4比较不用交换位置

第四轮8和3比较,交换位置,6和3比较交换位置,4和3比较交换位置,2和3比较不用交换位置

后面以此类推,都是向左比较到第一个元素,也就是当前元素左边都是有序的,右边都是无序的


5c45b6a2b2314090922ce75c3ab20823.jpg


6ebdfc2f1b8147bf88592b144a40c5af.jpg



035593b440b840d5be1a5c6044288718.jpg

3.插入排序代码实现

(1)整体编码实现

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {8,2,6,4,3,7,5};
        System.out.println("排序前:");
        System.out.println(Arrays.toString(arr));
        insertSort(arr);
        System.out.println("排序后:");
        System.out.println(Arrays.toString(arr));
    }
    public static void insertSort(int[] arr){
        //第一层循环,把数组分成两部分,左边是已将排好序的,右边是未排序的
        //当前下表左边的元素已经排好序,右边还未排序
        for (int i = 1; i < arr.length; i++) {
            //内层循环,从当前下标开始祥左比较,如果发现比左边元素小就惊醒交换
            //直到比较到左边第一个元素
            for (int j = i; j > 0; j--) {
                //依次交换,依次比较,如果不比前一个元素小,就跳出
                if(arr[j-1]>arr[j]){
                    int temp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                }else{
                    break;
                }
            }
            System.out.println("第 "+i+" 轮: "+Arrays.toString(arr));
        }
    }
}

(2)代码测试

084fa6d5c14d48a6a128e3065f663ea8.jpg

相关文章
|
1月前
|
机器学习/深度学习 算法 PyTorch
深度强化学习中SAC算法:数学原理、网络架构及其PyTorch实现
软演员-评论家算法(Soft Actor-Critic, SAC)是深度强化学习领域的重要进展,基于最大熵框架优化策略,在探索与利用之间实现动态平衡。SAC通过双Q网络设计和自适应温度参数,提升了训练稳定性和样本效率。本文详细解析了SAC的数学原理、网络架构及PyTorch实现,涵盖演员网络的动作采样与对数概率计算、评论家网络的Q值估计及其损失函数,并介绍了完整的SAC智能体实现流程。SAC在连续动作空间中表现出色,具有高样本效率和稳定的训练过程,适合实际应用场景。
140 7
深度强化学习中SAC算法:数学原理、网络架构及其PyTorch实现
|
2月前
|
算法 Java 数据库
理解CAS算法原理
CAS(Compare and Swap,比较并交换)是一种无锁算法,用于实现多线程环境下的原子操作。它通过比较内存中的值与预期值是否相同来决定是否进行更新。JDK 5引入了基于CAS的乐观锁机制,替代了传统的synchronized独占锁,提升了并发性能。然而,CAS存在ABA问题、循环时间长开销大和只能保证单个共享变量原子性等缺点。为解决这些问题,可以使用版本号机制、合并多个变量或引入pause指令优化CPU执行效率。CAS广泛应用于JDK的原子类中,如AtomicInteger.incrementAndGet(),利用底层Unsafe库实现高效的无锁自增操作。
理解CAS算法原理
|
3月前
|
算法 容器
令牌桶算法原理及实现,图文详解
本文介绍令牌桶算法,一种常用的限流策略,通过恒定速率放入令牌,控制高并发场景下的流量,确保系统稳定运行。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
令牌桶算法原理及实现,图文详解
|
2月前
|
存储 人工智能 缓存
【AI系统】布局转换原理与算法
数据布局转换技术通过优化内存中数据的排布,提升程序执行效率,特别是对于缓存性能的影响显著。本文介绍了数据在内存中的排布方式,包括内存对齐、大小端存储等概念,并详细探讨了张量数据在内存中的排布,如行优先与列优先排布,以及在深度学习中常见的NCHW与NHWC两种数据布局方式。这些布局方式的选择直接影响到程序的性能,尤其是在GPU和CPU上的表现。此外,还讨论了连续与非连续张量的概念及其对性能的影响。
79 3
|
3月前
|
机器学习/深度学习 人工智能 算法
探索人工智能中的强化学习:原理、算法与应用
探索人工智能中的强化学习:原理、算法与应用
|
3月前
|
负载均衡 算法 应用服务中间件
5大负载均衡算法及原理,图解易懂!
本文详细介绍负载均衡的5大核心算法:轮询、加权轮询、随机、最少连接和源地址散列,帮助你深入理解分布式架构中的关键技术。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
5大负载均衡算法及原理,图解易懂!
|
3月前
|
缓存 算法 网络协议
OSPF的路由计算算法:原理与应用
OSPF的路由计算算法:原理与应用
87 4
|
3月前
|
存储 算法 网络协议
OSPF的SPF算法介绍:原理、实现与应用
OSPF的SPF算法介绍:原理、实现与应用
109 3
|
3月前
|
机器学习/深度学习 人工智能 算法
探索人工智能中的强化学习:原理、算法及应用
探索人工智能中的强化学习:原理、算法及应用
|
4月前
|
算法 数据库 索引
HyperLogLog算法的原理是什么
【10月更文挑战第19天】HyperLogLog算法的原理是什么
187 1