热门标签 | HotTags
当前位置:  开发笔记 > 人工智能 > 正文

插入排序_动画|什么是插入排序?

篇首语:本文由编程笔记#小编为大家整理,主要介绍了动画 | 什么是插入排序?相关的知识,希望对你有一定的参考价值。 插入排序插入排序是比较简单也比较直接的一种排序算法。它是从一堆数据中取出一个数据并将

篇首语:本文由编程笔记#小编为大家整理,主要介绍了动画 | 什么是插入排序?相关的知识,希望对你有一定的参考价值。



插入排序

技术图片

插入排序是比较简单也比较直接的一种排序算法。它是从一堆数据中取出一个数据并将它插入到已排序的数据中合适的位置。

比如按身高排队,有一个人指挥排队从第二个人开始,按身高把当前的人安插到之前排序好队的合适的位置。

或者打扑克牌,假设我们拿到了10,J,K,A这四张牌,然后拿到了Q这张牌,那如何让手中的五张牌变为升序呢?如果我们只学了冒泡排序和快速排序,初始状态是10,J,K,A,Q。

如果是用冒泡排序或者快速排序去做的话,那就可能不合适。结果是对,但是浪费了很多比较次数。

正常人最简单的方式就是,把Q安插到J和K之间就可以了。

技术图片

插入排序正是如此,它的思想就是维护一个有序区,把元素一个一个插入到有序区中的合适的位置,直到所有元素有序为止。


视频动画





Code

技术图片


Result

初始状态 [5, 1, 3, 7, 4, 6, 2]

发生交换 [1, 5, 3, 7, 4, 6, 2]

1趟 [1, 5, 3, 7, 4, 6, 2]

发生交换 [1, 3, 5, 7, 4, 6, 2]

2趟 [1, 3, 5, 7, 4, 6, 2]

3趟 [1, 3, 5, 7, 4, 6, 2]

发生交换 [1, 3, 5, 4, 7, 6, 2]

发生交换 [1, 3, 4, 5, 7, 6, 2]

4趟 [1, 3, 4, 5, 7, 6, 2]

发生交换 [1, 3, 4, 5, 6, 7, 2]

5趟 [1, 3, 4, 5, 6, 7, 2]

发生交换 [1, 3, 4, 5, 6, 2, 7]

发生交换 [1, 3, 4, 5, 2, 6, 7]

发生交换 [1, 3, 4, 2, 5, 6, 7]

发生交换 [1, 3, 2, 4, 5, 6, 7]

发生交换 [1, 2, 3, 4, 5, 6, 7]

6趟 [1, 2, 3, 4, 5, 6, 7]


插入排序优化,减少不必要的交换次数

回顾一下上面代码运行的结果,发现有很多次的交换,会有一点一点的时间上的消耗。如果我们做减少交换次数的代码,那如何去写呢?

回顾一下快速排序那篇文章,也使用了减少交换次数的方法。它是一个一个待比较完之后,定位最大的元素或者最小的元素,然后进行交换。

插入排序把待插入的元素做一个标记,和有序区一个一个元素去做比较。假设是从待插入元素的邻近元素开始比较(从后往前),符合条件的前一个元素去复制粘贴到待插入元素的地址。直到不符合条件才插入到合适的位置。


视频动画





Code

技术图片


Result

初始状态 [5, 1, 3, 7, 4, 6, 2]

发生复制 [5, 5, 3, 7, 4, 6, 2]

1趟 [1, 5, 3, 7, 4, 6, 2]

发生复制 [1, 5, 5, 7, 4, 6, 2]

2趟 [1, 3, 5, 7, 4, 6, 2]

3趟 [1, 3, 5, 7, 4, 6, 2]

发生复制 [1, 3, 5, 7, 7, 6, 2]

发生复制 [1, 3, 5, 5, 7, 6, 2]

4趟 [1, 3, 4, 5, 7, 6, 2]

发生复制 [1, 3, 4, 5, 7, 7, 2]

5趟 [1, 3, 4, 5, 6, 7, 2]

发生复制 [1, 3, 4, 5, 6, 7, 7]

发生复制 [1, 3, 4, 5, 6, 6, 7]

发生复制 [1, 3, 4, 5, 5, 6, 7]

发生复制 [1, 3, 4, 4, 5, 6, 7]

发生复制 [1, 3, 3, 4, 5, 6, 7]

6趟 [1, 2, 3, 4, 5, 6, 7]


推荐阅读
  • 使用Numpy实现无外部库依赖的双线性插值图像缩放
    本文介绍如何仅使用Numpy库,通过双线性插值方法实现图像的高效缩放,避免了对OpenCV等图像处理库的依赖。文中详细解释了算法原理,并提供了完整的代码示例。 ... [详细]
  • 非公版RTX 3080显卡的革新与亮点
    本文深入探讨了图形显卡的进化历程,重点介绍了非公版RTX 3080显卡的技术特点和创新设计。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • Søren Kierkegaard famously stated that life can only be understood in retrospect but must be lived moving forward. This perspective delves into the intricate relationship between our lived experiences and our reflections on them. ... [详细]
  • 1:有如下一段程序:packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]
  • C++实现经典排序算法
    本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出,帮助读者全面了解这些排序方法的特点。 ... [详细]
  • 本文详细探讨了Java中的24种设计模式及其应用,并介绍了七大面向对象设计原则。通过创建型、结构型和行为型模式的分类,帮助开发者更好地理解和应用这些模式,提升代码质量和可维护性。 ... [详细]
  • 深入理解C++中的KMP算法:高效字符串匹配的利器
    本文详细介绍C++中实现KMP算法的方法,探讨其在字符串匹配问题上的优势。通过对比暴力匹配(BF)算法,展示KMP算法如何利用前缀表优化匹配过程,显著提升效率。 ... [详细]
  • golang常用库:配置文件解析库/管理工具viper使用
    golang常用库:配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库,是由大神SteveFrancia开发,他在google领导着golang的 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 探讨一个显示数字的故障计算器,它支持两种操作:将当前数字乘以2或减去1。本文将详细介绍如何用最少的操作次数将初始值X转换为目标值Y。 ... [详细]
  • 本文详细介绍了Java编程语言中的核心概念和常见面试问题,包括集合类、数据结构、线程处理、Java虚拟机(JVM)、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题,帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]
  • 本文探讨如何设计一个安全的加密和验证算法,确保生成的密码具有高随机性和低重复率,并提供相应的验证机制。 ... [详细]
  • 深入解析:手把手教你构建决策树算法
    本文详细介绍了机器学习中广泛应用的决策树算法,通过天气数据集的实例演示了ID3和CART算法的手动推导过程。文章长度约2000字,建议阅读时间5分钟。 ... [详细]
  • 在金融和会计领域,准确无误地填写票据和结算凭证至关重要。这些文件不仅是支付结算和现金收付的重要依据,还直接关系到交易的安全性和准确性。本文介绍了一种使用C语言实现小写金额转换为大写金额的方法,确保数据的标准化和规范化。 ... [详细]
author-avatar
靜trevis_263
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有