文档章节

插入排序详解

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
JAVA中运用数组的四种排序方法

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

闫三
2012/05/08
0
0
插入排序,希尔排序,堆排序详解

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

crazys_蘑菇
06/29
0
0
《Thinking in Algorithm》12.详解十一种排序算法

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

zh119893
2014/05/24
223
0
链表各类操作详解

仅供学习使用,附转载连接:http://blog.csdn.net/hackbuteer1/article/details/6591486 链表概述    链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要...

陈国成
2017/06/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

day96-20180923-英语流利阅读-待学习

英国王子也不看好人工智能,理由却和霍金不同 Daniel 2018-09-23 1.今日导读 2016 年 3 月 9 日至 15 日,世界围棋冠军李世石与谷歌研发的计算机围棋程序 AlphaGo 进行人机大战并以 1 比 4 ...

飞鱼说编程
21分钟前
1
0
今天在码云遇到一个很有意思的人 for Per.js

今天在码云遇到一个很有意思的人,他在我的Per.js项目下面评论了一句,大意为“你试试这句代码,看看速度到底是你快还是Vue快”【当然,这个评论被我手残不小心删掉了...】。 然后我就试了,...

Skyogo
26分钟前
23
0
Java -------- 首字母相关排序总结

Java 字符串数组首字母排序 字符串数组按首字母排序:(区分大小写) String[] strings = new String[]{"ba","aa","CC","Ba","DD","ee","dd"}; Arrays.sort(strings); for (int i ...

切切歆语
28分钟前
1
0
还在用 Git 的 -f 参数强推仓库,你这是在作死!

最近,美国一个程序员因为同事不写注释,代码不规范,最严重的是天天使用 git push -f 参数强行覆盖仓库,该程序员忍无可忍向四名同事开抢,其中一人情况危急!!! 不写注释、代码不规范是一...

红薯
41分钟前
347
0
NPM报错终极大法

所有的错误基本上都跟node的版本相关 直接删除系统中的node 重新安装 sudo rm -rf /usr/local/{bin/{node,npm},lib/node_modules/npm,lib/node,share/man/*/node.*} 重新安装 $ n lts$ npm...

lilugirl
45分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部