首页 > 其他分享 >有趣的插入排序

有趣的插入排序

时间:2023-05-01 22:04:00浏览次数:56  
标签:temp 插入排序 元素 无序 insertionSort 有序 有趣 复杂度

原文点此跳转

什么是插入排序(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),因为没有使用线性增长的数据结构。

原文点此跳转

标签:temp,插入排序,元素,无序,insertionSort,有序,有趣,复杂度
From: https://blog.51cto.com/u_12639291/6239410

相关文章

  • 一些有趣的题目 - 1
    \(1.\)如图所示,一硬杆\(AB\)竖立靠在墙角,受外力作用下滑,顶部与底部始终接触墙面和地面,直至完全倒下.若杆长为\(L\),粗细不计,求杆扫过的图形的面积以及围成此图形的一段曲线的函数解析式.\(\large\calMy\Solve:\)设在杆下滑时的某一时刻,杆上端\(A\)位于\((0,y_o)......
  • GitHub 上有趣、入门级的开源项目HelloGitHub 升级版的 MiniGPT-4 搞定基于图片的文
    GitHub上有趣、入门级的开源项目HelloGitHub  https://github.com/521xueweihan/HelloGitHubhttps://github.com/521xueweihan/HelloGitHub/blob/master/content/HelloGitHub61.md 这里有实战项目、入门教程、黑科技、开源书籍、大厂开源项目等,涵盖多种编程语言Python......
  • 一个有趣的图片加载效果
    日常在业务中会经常使用到图片,而涉及到一些大图的加载等待的时间较长,一般为了用户更好的体验,会使用一些不同的图片加载效果,比如以下几种情况:骨架屏:在页面上用占位框架代替图片,展示出图片的大致结构和区域,给用户一种“正在加载”的视觉体验。进度条:用进度条的形式展示图片的加......
  • 四种语言刷算法之对链表进行插入排序
    力扣147. 对链表进行插入排序1、C/***Definitionforsingly-linkedlist.*structListNode{*intval;*structListNode*next;*};*/structListNode*insertionSortList(structListNode*head){structListNode*newHead=head;struc......
  • Java中常用排序算法及示例-冒泡排序、希尔排序、选择排序、插入排序、合并排序、基数
    场景Java中需要对数据进行排序处理,常用的排序算法以及示例进行归纳整理。注:实现1、冒泡排序冒泡排序法又称为交换排序法,原理是从第一个元素开始,比较相邻元素的大小,若大小顺序有误,则对调后再进行下一个元素的比较。如此扫描一次之后就可以确保最后一个元素位于正确的顺序,接着逐步进......
  • 排序算法-插入排序
    排序算法-插入排序1.直接插入排序InsertSort1.1InsertSort介绍InsertSort也是一种简单的内部排序算法,其是对待排序的元素以插入的方式寻找该元素的适当位置,以达到排序的目的,是一种稳定的排序算法。InserSort的基本思想是:将待排序序列看作一个有序表和一个无序表,初始时......
  • Java中常用排序算法及示例-冒泡排序、希尔排序、选择排序、插入排序、合并排序、基数
    场景Java中需要对数据进行排序处理,常用的排序算法以及示例进行归纳整理。注:博客:https://blog.csdn.net/badao_liumang_qizhi实现1、冒泡排序冒泡排序法又称为交换排序法,原理是从第一个元素开始,比较相邻元素的大小,若大小顺序有误,则对调后再进行下一个元素的比较。如此扫描......
  • 有趣的toFixed
    在我们正常的思维看来,toFixed是四舍五入的,但是会出现例外,如:   发现5.215的toFixed并不是5.22,其实这个的原理类似于0.1+0.2≠0.3是一个原理,如:  发现5.215的底层是5.12499999999...,那么此时按照奇进偶舍的规则,第三位4小于5直接舍弃,就成了5.21。所以这里就说得通了。。......
  • 手撕排序算法之插入排序
    前言排序算法是一种算法思想,插入排序有两种,直接插入排序和希尔排序,后者可以看作是前者的优化,因为它完完全全采用的是插入排序算法一、直接插入排序分两种情况,1.1简单插入排序在一个已经有序的数组里插入一个数据,使其依旧有序,只需要对一个元素进行插入排序,进行一次插入排序假如数组......
  • 力扣620(MySQL)-有趣的电影(简单)
    题目:某城市开了一家新的电影院,吸引了很多人过来看电影。该电影院特别注意用户体验,专门有个LED显示板做电影推荐,上面公布着影评和相关电影描述。作为该电影院的信息部主管,您需要编写一个SQL查询,找出所有影片描述为非 boring (不无聊) 的并且id为奇数 的影片,结果请按等级......