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


推荐阅读
  • 本文节选自《NLTK基础教程——用NLTK和Python库构建机器学习应用》一书的第1章第1.2节,作者Nitin Hardeniya。本文将带领读者快速了解Python的基础知识,为后续的机器学习应用打下坚实的基础。 ... [详细]
  • 本文总结了《编程珠玑》第12章关于采样问题的算法描述与改进,并提供了详细的编程实践记录。参考了其他博主的总结,链接为:http://blog.csdn.net/neicole/article/details/8518602。 ... [详细]
  • 非计算机专业的朋友如何拿下多个Offer
    大家好,我是归辰。秋招结束后,我已顺利入职,并应公子龙的邀请,分享一些秋招面试的心得体会,希望能帮助到学弟学妹们,让他们在未来的面试中更加顺利。 ... [详细]
  • 双指针法在链表问题中应用广泛,能够高效解决多种经典问题,如合并两个有序链表、合并多个有序链表、查找倒数第k个节点等。本文将详细介绍这些应用场景及其解决方案。 ... [详细]
  • PHP实现汉诺塔算法
    昨天研究了一天汉诺塔算法都没搞懂,感觉自己智商被碾压了,还不如《猩球崛起》中的那一只猩猩!!!起源传说最早发明这个问题的人是法国数学家『爱德华·卢卡斯』。在世界中心贝拿勒斯(在印度 ... [详细]
  • 本文介绍如何使用OpenCV和线性支持向量机(SVM)模型来开发一个简单的人脸识别系统,特别关注在只有一个用户数据集时的处理方法。 ... [详细]
  • 本文介绍了如何通过路由汇总和无类域间路由(CIDR)技术来优化路由表,减少路由条目数量,提高网络效率。具体案例展示了路由汇总的实现方法及其对网络性能的影响。 ... [详细]
  • 本文介绍了如何使用Visual Studio Code、Sublime Text等编辑器批量删除MATLAB代码中的注释和空行,同时提供了一些高级技巧以确保代码的整洁。 ... [详细]
  • 本文介绍了几种常用的图像相似度对比方法,包括直方图方法、图像模板匹配、PSNR峰值信噪比、SSIM结构相似性和感知哈希算法。每种方法都有其优缺点,适用于不同的应用场景。 ... [详细]
  • LintCode 1218. 计算补数的 JavaScript 算法
    本题要求给定一个正整数,计算其补数。补数是指将该数字的二进制表示逐位取反,然后转换回十进制得到的新数。 ... [详细]
  • 根据经济日报的报道,截至3月15日,包括抖音、今日头条、微信、淘宝、百度、大众点评、微博和小红书在内的多个主流App已经上线了算法关闭功能,用户可以在后台一键关闭“个性化推荐”。 ... [详细]
  • MATLAB实现Sobel边缘检测算法
    图像边缘是指图像中灰度值发生显著变化的区域。Sobel算子是一种常用的边缘检测方法,通过计算图像灰度值的梯度来检测边缘。本文介绍了Sobel算子的基本原理,并提供了基于MATLAB的实现代码。 ... [详细]
  • 本文详细介绍了如何使用OpenSSL自建CA证书的步骤,包括准备工作、生成CA证书、生成服务器待签证书以及证书签名等过程。 ... [详细]
  • Ihavetwomethodsofgeneratingmdistinctrandomnumbersintherange[0..n-1]我有两种方法在范围[0.n-1]中生 ... [详细]
  • 本文详细介绍了在 Ubuntu 系统上搭建 Hadoop 集群时遇到的 SSH 密钥认证问题及其解决方案。通过本文,读者可以了解如何在多台虚拟机之间实现无密码 SSH 登录,从而顺利启动 Hadoop 集群。 ... [详细]
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社区 版权所有