什么是插入排序?

菜园前端
• 阅读 418

原文链接:https://note.noxussj.top/?source=helloworld


什么是插入排序(insertionSort)?

在数组中从左到右依次取一个数出来,然后把它放到合适的位置。从思想上可以分为有序区和无序区,有序区在左边代表已经排列好的元素。

算法步骤

  1. 默认左边第一个元素已经在有序区了
  2. 在无序区取一个数出来(第二个元素)
  3. 遍历有序区元素,把取出来的元素放到合适的位置上
  4. 以此类推,执行 n - 1 轮(无序区为空时)
  5. 完成排序

动画演示链接

https://visualgo.net/zh/sorting

什么是插入排序?

基础案例

  • 时间复杂度:O (n ^ 2)
  • 空间复杂度:O (1)
Array.prototype.insertionSort = function () {
    for (let i = 1; i < this.length; i++) {
        const temp = this[i]

        let j = i

        while (j > 0) {
            if (this[j - 1] > temp) {
                this[j] = this[j - 1]
            } else {
                break
            }

            j--
        }

        this[j] = temp
    }
}

const arr = [5, 4, 3, 2, 1]

arr.insertionSort() // [1, 2, 3, 4, 5]

因为存在两个嵌套循环,所以时间复杂度是 O (n ^ 2),而时间复杂度是 O (1),因为没有使用线性增长的数据结构。

点赞
收藏
评论区
推荐文章
Easter79 Easter79
3年前
swap空间的增减方法
(1)增大swap空间去激活swap交换区:swapoff v /dev/vg00/lvswap扩展交换lv:lvextend L 10G /dev/vg00/lvswap重新生成swap交换区:mkswap /dev/vg00/lvswap激活新生成的交换区:swapon v /dev/vg00/lvswap
22 22
3年前
【排序算法动画解】直接插入排序
本文为系列专题的第14篇文章。1.2.3.4.5.6.7.8.9.10.11.12.13.前面介绍了已经介绍了三种排序,暴力排序、冒泡排序和简单选择排序,一个共同点都是基于交换。我们可以用另一种视角来看待排序,即将一个待排序的数组看成两个部分:有序区和乱序区。在排序开始前,整个数组都是乱序区,而有序区则为空:排序开始后,有序区
Peter20 Peter20
3年前
mysql中like用法
like的通配符有两种%(百分号):代表零个、一个或者多个字符。\(下划线):代表一个数字或者字符。1\.name以"李"开头wherenamelike'李%'2\.name中包含"云",“云”可以在任何位置wherenamelike'%云%'3\.第二个和第三个字符是0的值wheresalarylike'\00%'4\
Easter79 Easter79
3年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
3年前
C语言自学《五》
什么是数组数组是一组数目固定、类型相同的数据项数组中的数据称为元素比如longnumbers\10\;方括号中的数字定义了要存放在数组中的元素个数,称为数组维度数组有一个类型,它组合了元素的类型和数组中的元素个数,因此如果两个数组的元素个数、类型相同,这两个数组的类型就相同可以在数组名称后的方括号内使用索引值,索引值是从0开始
Wesley13 Wesley13
3年前
Java基础语法:数组
一、简介描述:数组是相同类型数据的有序集合。其中,每一个数据称作一个数组元素,每个数组元素可以通过一个下标来访问它们。基本特点:1.数组的长度是确定的。数组一旦被创建,它的大小就是不可以改变的。2.数组元素必须是相同类型,不允许
菜园前端 菜园前端
1年前
什么是选择排序?
原文链接:什么是选择排序(selectSort)?选择排序就是在一个排列中划分为有序区和无序区,有序区在左边,无序区在右边。首先在无序区中找到最小元素,存放到有序区的起始位置,然后再从剩余的无序区中继续寻找最小元素,然后放到有序区的末尾。以此类推,直到无序
菜园前端 菜园前端
1年前
什么是二分搜索?
原文链接:什么是二分搜索?二分搜索是一种比较高效的搜索算法,但前提必须是有序数组。主要步骤如下:1.从数组的中间元素开始,如果中间元素正好是目标值,则搜索结束2.如果目标值大于或者小于中间元素,则在大于或者小于中间元素的那一半数组中继续二分搜索基础案例时间
分布式系统的主键生成方案对比 | 京东云技术团队
UUID​UUID(通用唯一识别码)是由32个十六进制数组成的无序字符串,通过一定的算法计算出来。为了保证其唯一性,UUID规范定义了包括网卡MAC地址、时间戳、名字空间(Namespace)、随机或伪随机数、时序等元素,以及从这些元素生成UUID的算法。