看完这个你还不会 插入排序 么

前言

由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画来描述常见的数据结构和算法。本系列包括十大排序、堆、队列、树、并查集、图等等大概几十篇。

插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

算法步骤

  1. 将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
  2. 从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)。

来源:https://github.com/hustcc/JS-Sorting-Algorithm

算法演示

排序动画过程解释

  1. 一开始左端数字已经排序,数字 5 不动
  2. 然后,取出剩余未操作的左端数字 3
  3. 将其与已经操作的左侧数字相比较
  4. 如果左边的数字较大,则交换两个数字
  5. 这种情况下,由于 5 大于 3 ,所以交换两个数字
  6. 重复此操作,直到出现一个较小的数字或者数字到达左端
  7. 数字 3 已经完成排序
  8. 接下来,和之前一样取出剩余未操作的左端数字 4
  9. 与其相邻的左边数字进行比较
  10. 这种情况下,由于 5 大于 4 ,所以交换两个数字
  11. 继续操作,由于 3 小于 4 ,即出现了更小的数字,所以 4 停止移动
  12. 数字 4 已经完成排序
  13. 重复相同的操作,直到所有的数字完成排序

代码实现

为了更好的让读者用自己熟悉的编程语言来理解动画,笔者将贴出多种编程语言的参考代码,代码全部来源于网上。

C++代码实现

Java代码实现

Python代码实现

JavaScript代码实现

如果你是iOS开发者,可以在GitHub上 https://github.com/MisterBooo/Play-With-Sort-OC 获取更直观可调试运行的源码。

你可以关注公众号 五分钟学算法 获取更多排序内容。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我是攻城师

Scala中的case match语法

2583
来自专栏数据结构与算法

1470 数列处理

个人博客:doubleq.win 1470 数列处理  时间限制: 1 s  空间限制: 1000 KB  题目等级 : 青铜 Bronze 题解 题目描述 D...

2715
来自专栏python3

python3--小数据池,is,字符编码

python3x中的str在内存中的编码方式是unicode. python3x中的str不能直接存储和发送

1741
来自专栏用户2442861的专栏

STL list源码分析以及实现

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/d...

943
来自专栏前端学习心得

ES6核心特性(二)

1583
来自专栏鸿的学习笔记

一句话讲明白基本排序

412
来自专栏MelonTeam专栏

OpenGL ES读书笔记(一)—初始庐山真面目

1. OpenGL ES简介 OpenGL ES(OpenGL for Embedded Systems)是以手持和嵌入式设备为目标的高级3D图形应用程序编程接...

24910
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版6.3节有成员变量的类coredump例子

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

1051
来自专栏梧雨北辰的开发录

Swift学习:泛型

本篇将详细总结介绍Swift泛型的用法; Swift泛型代码让你能够根据自定义的需求,编写出适用于任意类型、灵活可重用的函数及类型。它能让你避免代码的重复,用...

842
来自专栏我的技术专栏

关于传值与传引用的讨论

对于用户自定义的类型来说,传引用一般要比传值高效。传引用不需要经过对象构造的过程,在《Effective C++》中作者举了个例子:

1075

扫码关注云+社区