热门标签 | 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]


推荐阅读
  • 非公版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种设计模式及其应用,并介绍了七大面向对象设计原则。通过创建型、结构型和行为型模式的分类,帮助开发者更好地理解和应用这些模式,提升代码质量和可维护性。 ... [详细]
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • 计算机网络复习:第五章 网络层控制平面
    本文探讨了网络层的控制平面,包括转发和路由选择的基本原理。转发在数据平面上实现,通过配置路由器中的转发表完成;而路由选择则在控制平面上进行,涉及路由器中路由表的配置与更新。此外,文章还介绍了ICMP协议、两种控制平面的实现方法、路由选择算法及其分类等内容。 ... [详细]
  • 本文将介绍如何使用 Go 语言编写和运行一个简单的“Hello, World!”程序。内容涵盖开发环境配置、代码结构解析及执行步骤。 ... [详细]
  • 本文详细介绍了如何使用PHP检测AJAX请求,通过分析预定义服务器变量来判断请求是否来自XMLHttpRequest。此方法简单实用,适用于各种Web开发场景。 ... [详细]
  • 线性Kalman滤波器在多自由度车辆悬架主动控制中的应用研究
    本文探讨了线性Kalman滤波器(LKF)在不同自由度(2、4、7)的车辆悬架系统中进行主动控制的应用。通过详细的仿真分析,展示了LKF在提升悬架性能方面的潜力,并总结了调参过程中的关键要点。 ... [详细]
  • 本文探讨了Hive中内部表和外部表的区别及其在HDFS上的路径映射,详细解释了两者的创建、加载及删除操作,并提供了查看表详细信息的方法。通过对比这两种表类型,帮助读者理解如何更好地管理和保护数据。 ... [详细]
  • 本文介绍如何利用动态规划算法解决经典的0-1背包问题。通过具体实例和代码实现,详细解释了在给定容量的背包中选择若干物品以最大化总价值的过程。 ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
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社区 版权所有