您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

插入排序算法,就这么简单,还学不会算我输

时间:2019-11-21 11:11:09  来源:  作者:

一、前言

什么是算法?算法是某种集合,是简单指令的集合,是被指定的简单指令集合。确定该算法重要的指标:

  • 第一是否能解决问题;
  • 第二算法运行时间,即解决问题出结果需要多少时间;
  • 还有所需的空间资源,比如内存等。

很多时候,写一个工作程序并不够。因为遇到大数据下,运行时间就是一个重要的问题。

算法性能用大 O 标记法表示。大 O 标记法是标记相对增长率,精度是粗糙的。比如 2N 和 3N + 2 ,都是 O(N)。也就是常说的线性增长,还有常说的指数增长等

典型的增长率

插入排序算法,就这么简单,还学不会算我输

 

典型的提供性能做法是分治法,即分支 divide and conquer 策略:

  1. 将问题分成两个大致相等的子问题,递归地对它们求解,这是分的部分;
  2. 治阶段将两个子问题的解修补到一起,并可能再做些少量的附加工作,最后得到整个问题的解。
插入排序算法,就这么简单,还学不会算我输

 

二、排序

插入排序算法,就这么简单,还学不会算我输

 

排序问题,是古老,但一直流行的问题。从 ACM 接触到现在工作,每次涉及算法,或品读 JDK 源码中一些算法,经常会有排序的算法出现。

排序算法是为了将一组数组(或序列)重新排列,排列后数据符合从大到小(或从小到大)的次序。这样数据从无序到有序,会有什么好处?

  • 应用层面:解决问题。
  • 最简单的是可以找到最大值或者最小值
  • 解决"一起性"问题,即相同标志元素连在一起
  • 匹配在两个或者更多个文件中的项目
  • 通过键码值查找信息
  • 系统层面:减少系统的熵值,增加系统的有序度 (Donald Knuth 的经典之作《计算机程序设计艺术》(The Art of Computer Programming)的第三卷)

通过维基百科查阅资料得到:在主内存中完成的排序叫做,内部排序。那需要在磁盘等其他存储完成的排序,叫做外部排序 external sorting。

接口是一个抽象类型,是抽象方法(compareTo)的集合,用 interface 来声明。因此被排序的对象属于 Comparable 类型,即实现 Comparable 接口,然后调用对象实现的 compareTo 方法进行比较后排序。

在这些条件下的排序,叫作基于比较的排序(comparison-based sorting)

三、插入排序

白话文:熊大(一)、熊二、熊三... 按照身高从低到高排队(排序)。这时候熊 N 加入队伍,它从队伍尾巴开始比较。如果它比前面的熊身高低,则与被比较的交换位置,依次从尾巴到头部进行比较 & 交换位置。最终换到了应该熊 N 所在的位置。这就是插入排序的原理。

插入排序(insertion sort)

  • 最简单的排序之一。ps: 冒泡排序看看就好,不推荐学习
  • 由 N - 1 次排序过程组成。
  • 如果被排序的这样一个元素,就不需要排序。即 N =1 (1 - 1 = 0)
  • 每一次排序保证,从第一个位置到当前位置的元素为已排序状态。
  • 如图:每个元素往前进行比较,并终止于自己所在的位置
插入排序算法,就这么简单,还学不会算我输

 


插入排序算法,就这么简单,还学不会算我输

 

代码解析如下:

  • 从数组的第二个元素,向前开始比较。比第一个元素小,则交换位置
  • 如果第二个元素比较完毕,那就第三个,第四个... 以此类推
  • 比较到最后一个元素时,完成排序

时间复杂度是 O(N^2),最好情景的是排序已经排好的,那就是 O(N),因为满足不了循环的判断条件;最极端的是反序的数组,那就是 O(N^2)。所以该算法的时间复杂度为 O(N^2)

运行 main 方法,结果如下:

[2, 3, 1, 4, 3]
[1, 2, 3, 3, 4]

再考虑考虑优化,会怎么优化呢?插入排序优化版 不是往前比较 。往前的一半比较,二分比较会更好。具体代码,可以自行试试

四、Array.sort 源码中的插入排序

上面用自己实现的插入算法进行排序,其实 JDK 提供了 Array.sort 方法,方便排序。案例代码如下:

插入排序算法,就这么简单,还学不会算我输

 

运行 main 方法,结果如下:

[2, 3, 1, 4, 3]
[1, 2, 3, 3, 4]

那 Arrays.sort 是如何实现的呢?JDK 1.2 的时候有了 Arrays ,JDK 1.8 时优化了一版 sort 算法。大致如下:

  • 如果元素数量小于 47,使用插入排序
  • 如果元素数量小于 286,使用快速排序
  • Timsort 算法整合了归并排序和插入排序
插入排序算法,就这么简单,还学不会算我输

 

源码中我们看到了 mergeSort 里面整合了插入排序算法,跟上面实现的异曲同工。这边就不一行一行解释了。

五、小结

算法是解决问题的。所以不一定一个算法解决一个问题,可能多个算法一起解决一个问题。达到问题的最优解。插入排序,这样就这么简单



Tags:排序算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15  Tags: 排序算法  点击:(16)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  Tags: 排序算法  点击:(40)  评论:(0)  加入收藏
1. 插入排序步骤:1.从第一个元素开始,该元素可以认为已经被排序2.取下一个元素tem,从已排序的元素序列从后往前扫描3.如果该元素大于tem,则将该元素移到下一位4.重复步骤3,直到找...【详细内容】
2021-08-19  Tags: 排序算法  点击:(100)  评论:(0)  加入收藏
人生有涯,学海无涯今天跟大家分享一个常用的排序算法——快速排序。我想大家在日常的工作或者面试的时候肯定经常会遇到很多排序算法,而且快速排序算法往往是这里面...【详细内容】
2021-03-04  Tags: 排序算法  点击:(182)  评论:(0)  加入收藏
1. 冒泡排序算法实现(javascript)//冒泡排序算法(javascript)//author:Hengda//arr数组//mode false 升序 ture 降序function bubbleSort( arr, mode ){ var i, j, temp, l...【详细内容】
2021-02-07  Tags: 排序算法  点击:(220)  评论:(0)  加入收藏
用希尔排序法对一组数据由小到大进行排序,数据分别为 69、56、12、136、3、55、46、 99、88、25。例子:(1)自定义函数 shsort(),实现希尔排序。(2) main() 函数作为程序的入口...【详细内容】
2021-01-25  Tags: 排序算法  点击:(216)  评论:(0)  加入收藏
选择排序 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续...【详细内容】
2020-11-19  Tags: 排序算法  点击:(173)  评论:(0)  加入收藏
今天我们就来讨论面试官最喜欢问到的排序算法吧,从冒泡排序、选择排序、插入排序等十大排序算法的排序步骤、代码实现两个方面入手,彻底搞清实现原理,保证面试道路一路畅通。0...【详细内容】
2020-07-26  Tags: 排序算法  点击:(97)  评论:(0)  加入收藏
今天我们就来讨论面试官最喜欢问到的排序算法吧,从冒泡排序、选择排序、插入排序等十大排序算法的排序步骤、代码实现两个方面入手,彻底搞清实现原理,保证面试道路一路畅通。01...【详细内容】
2020-07-25  Tags: 排序算法  点击:(62)  评论:(0)  加入收藏
1 插入排序算法定义插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好...【详细内容】
2020-06-30  Tags: 排序算法  点击:(55)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯·奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条