文档章节

插入排序详解

fengsehng
 fengsehng
发布于 2016/11/09 09:11
字数 835
阅读 0
收藏 0

概述

有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。

基本思想

插入排序的基本思想是:每步将一个待排序的纪录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。

步骤

⒈从有序数列和无序数列{a2,a3,…,an}开始进行排序;

⒉处理第i个元素时(i=2,3,…,n),数列{a1,a2,…,ai-1}是已有序的,而数列{ai,ai+1,…,an}是无序的。用ai与ai-1,a i-2,…,a1进行比较,找出合适的位置将ai插入;

⒊重复第二步,共进行n-i次插入处理,数列全部有序。

代码

/** *插入排序 *@paramarr *@return */
private static int[] insertSort(int[]arr){
if(arr == null || arr.length < 2){
    return arr;
}
for(inti=1;i<arr.length;i++){
for(intj=i;j>0;j--){
if(arr[j]<arr[j-1]){
//TODO:
int temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}else{
//接下来是无用功
break;
}
}
}
return arr;
}

复杂度

如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法的时间复杂度为O(n^2)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。

稳定性

插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列## 我的微信二维码如下,欢迎交流讨论 ##
这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧

微信订阅号二维码如下:

这里写图片描述的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

© 著作权归作者所有

共有 人打赏支持
fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
私信 提问
JAVA中运用数组的四种排序方法

JAVA中在运用数组进行排序功能时,一般有四种方法:快速排序法、冒泡法、选择排序法、插入排序法。 快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。 冒泡法是运用遍历数组进...

IceRainYWC
2014/03/17
0
0
插入排序,希尔排序,堆排序详解

本文将介绍三种排序算法--插入排序,希尔排序,堆排序。本文所有例子都是使用升序 一.插入排序 算法思想 维护一个有序数组,将要插入的数据与有序数组自最后一个元素直到合适位置的数一一比较...

crazys_蘑菇
06/29
0
0
JAVA中运用数组的四种排序方法

JAVA中在运用数组进行排序功能时,一般有四种方法:快速排序法、冒泡法、选择排序法、插入排序法。 快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。 冒泡法是运用遍历数组进...

闫三
2012/05/08
0
0
为什么说算法是程序猿“修仙”的必经之地?

作者 | 菜鸟奋斗史 责编 | 胡巍巍 算法主要衡量标准 1、时间复杂度(运行时间) 在算法时间复杂度维度,我们主要对比较和交换的次数做对比,其他不交换元素的算法,主要会以访问数组的次数的...

CSDN资讯
11/23
0
0
《Thinking in Algorithm》12.详解十一种排序算法

排序算法在算法中占着很重要的地位,很多算法的实现都是基于排序算法的(如搜索算法和合并算法)。所以排序算法也是笔试面试中必考内容。但是不管他怎么考,也就是那几种算法,一般不会超出我...

zh119893
2014/05/24
223
0

没有更多内容

加载失败,请刷新页面

加载更多

numpy常用操作

水平合并数组 import numpy as npa = [1,2,3]b = [4,5,6]np.hstack((a,b))# array([1, 2, 3, 4, 5, 6])c = [a,['a','b','c']]d = [b,['d','e','f']]np.hstack((c,d))#array([['1'......

datadev_sh
20分钟前
2
0
四种检测异常值的常用技术简述

摘要: 本文介绍了异常值检测的常见四种方法,分别为Numeric Outlier、Z-Score、DBSCAN以及Isolation Forest 在训练机器学习算法或应用统计技术时,错误值或异常值可能是一个严重的问题,它们...

阿里云官方博客
23分钟前
2
0
如何删除本地服务

Microsoft Windows [版本 10.0.17134.407] (c) 2018 Microsoft Corporation。保留所有权利。 C:\WINDOWS\system32>SC 描述: SC 是用来与服务控制管理器和服务进行通信 的命令行程序。 用法:...

码农屌丝
35分钟前
2
0
Web安全学习规划

一名合格的Web安全工程师是要具备很多的知识点,不但要对网站架构熟悉,通讯协议,测试流程与测试工具使用,漏洞利用脚本编写,还有需要经验的积累等。 互联网进入下半场,竞争越发的激烈,能...

Linux就该这么学
40分钟前
1
0
爬虫Requests基本使用

Requests基本使用 安装 pip install requests 一、Requests模块请求 获取网页(不带参数) r = requests.get('http://www.chinahufei.com')r = requests.post('http://www.chinahufei.com')......

chinahufei
41分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部