排序算法---插入排序-----详解&&代码

简介: 排序算法---插入排序-----详解&&代码

插入排序:

插入排序的思路也很简单:假设前面已经有i节点是有序的,那么就从第i+1个节点开始,插入到前面的i个节点的合适的位置中。由于第一个元素自身总是有序的,因此从第2个开始,不断插入前面的有序序列,直到全部排列完毕。



假设总共有n个节点,那么总共需要将n−1个节点插入到有序序列中,而插入节点时需要找到合适的位置,显然这个查找的过程时间复杂度是O(n−i),因此插入排序的时间复杂度是O(n−1)(n−i),即O(n^2)。


原始数据(80,50,20,30,2,18,100)

第一次排序:(50,80,20,30,2,18,100)

第二次排序:(20,50,80,30,2,18,100)

第三次排序:(20,30,50,80,2,18,100)

第四次排序:(2,20,30,50,80,18,100)

第五次排序:(2,18,20,30,50,80,100)

代码:(第一种方法)

void Insertsort(int data[], int len)
{
    int i, j;
    int temp;
    //插入排序
    for (i = 1; i < len; i++)
    {
        temp = data[i]; //备份
        //循环比较插入到指定位置
        for (j = i; j > 0; j--)
        {
            if (data[j] < data[j - 1])
            {
                data[j] = data[j - 1];
                data[j - 1] = temp;
            }
            else
                break;
        }
    }
}

代码:(第二种方法)

//就是默认第一个是有序的,后边是无序的,把后边无序的每个数插入到前面有序中,有序的越来越多,无序的越来越少。
//先找到有序数列的位置,然后插进去再把后边的数后移
void Insertsort1(int data[], int len)
{
    //1.把无序的数找到在有序数列的位置
    //0~i-1是无序的,i~是有序的
    int i, j, k;
    int temp;
    for (i = 1; i < len; i++)
    {
        //i是无序数列中第一个数,遍历有序数列
        for (j = 0; j < i; j++)
        {
            //找到位置了,j就是要插入的位置下标
            if (data[i] < data[j])
            {
                //k = j;
                temp = data[i];
                //把j后边的数往后挪
                /*for (; j < len; j++)
                    data[j+1] = data[j];*/
                for (k = i - 1; k >= j; k--) //a[j] ~ a[i-1]所有的元素往后挪动一位
                {
                    data[k + 1] = data[k];
                }
                data[j] = temp;
            }
        }
    }
}
目录
打赏
0
0
0
0
27
分享
相关文章
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
本文聚焦 MySQL 集群架构中的负载均衡算法,阐述其重要性。详细介绍轮询、加权轮询、最少连接、加权最少连接、随机、源地址哈希等常用算法,分析各自优缺点及适用场景。并提供 Java 语言代码实现示例,助力直观理解。文章结构清晰,语言通俗易懂,对理解和应用负载均衡算法具有实用价值和参考价值。
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
这个AI把arXiv变成代码工厂,快速复现顶会算法!Paper2Code:AI论文自动转代码神器,多智能体框架颠覆科研复现
Paper2Code是由韩国科学技术院与DeepAuto.ai联合开发的多智能体框架,通过规划、分析和代码生成三阶段流程,将机器学习论文自动转化为可执行代码仓库,显著提升科研复现效率。
341 19
这个AI把arXiv变成代码工厂,快速复现顶会算法!Paper2Code:AI论文自动转代码神器,多智能体框架颠覆科研复现
18个常用的强化学习算法整理:从基础方法到高级模型的理论技术与代码实现
本文系统讲解从基本强化学习方法到高级技术(如PPO、A3C、PlaNet等)的实现原理与编码过程,旨在通过理论结合代码的方式,构建对强化学习算法的全面理解。
170 10
18个常用的强化学习算法整理:从基础方法到高级模型的理论技术与代码实现
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
近端策略优化(PPO)是深度强化学习中高效的策略优化方法,广泛应用于大语言模型的RLHF训练。PPO通过引入策略更新约束机制,平衡了更新幅度,提升了训练稳定性。其核心思想是在优势演员-评论家方法的基础上,采用裁剪和非裁剪项组成的替代目标函数,限制策略比率在[1-ϵ, 1+ϵ]区间内,防止过大的策略更新。本文详细探讨了PPO的基本原理、损失函数设计及PyTorch实现流程,提供了完整的代码示例。
2021 10
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
JavaScript 中通过Array.sort() 实现多字段排序、排序稳定性、随机排序洗牌算法、优化排序性能,JS中排序算法的使用详解(附实际应用代码)
Array.sort() 是一个功能强大的方法,通过自定义的比较函数,可以处理各种复杂的排序逻辑。无论是简单的数字排序,还是多字段、嵌套对象、分组排序等高级应用,Array.sort() 都能胜任。同时,通过性能优化技巧(如映射排序)和结合其他数组方法(如 reduce),Array.sort() 可以用来实现高效的数据处理逻辑。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
193 1
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
通过优化算法和代码结构来提升易语言程序的执行效率
通过优化算法和代码结构来提升易语言程序的执行效率
193 2
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。

热门文章

最新文章

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问