文档章节

排序算法笔记:插入排序 InsertionSort

CheN_exe
 CheN_exe
发布于 2014/01/04 13:40
字数 150
阅读 25
收藏 0
/**
 * 插入排序
 * 简述:
 * 		获取array[i],并将array[i]插入于array[j+1]处,其中j<=i,并且array[j]<array[i] && array[j+1]>=array[i]
 * 时间复杂度:
 * 		Θ(n^2)
 * 空间复杂度:
 * 		O(1)
 * 优点:
 * 		
 * 缺点:
 * 		
 * 可改进:
 * 		
 * @author CheN
 * 
 */
public class InsertionSort {
	/**
	 * 正序
	 * @param array
	 * @return
	 */
	public static int[] asc( int[] array ) {
		for (int i = 1; i < array.length ; i++) {
			int key = array[i];
			int j = i - 1;
			//若key小于array[j],则将array[j]向后挪一位
			while ( j >= 0 && array[j] > key ) {
				array[j + 1] = array[j];
				j = j - 1;
			}
			array[j + 1] = key;
		}
		return array;
	}
}


若有错误或不妥之处,敬请谅解并指点。

© 著作权归作者所有

共有 人打赏支持
CheN_exe
粉丝 2
博文 40
码字总数 17192
作品 0
海淀
程序员
私信 提问
算法分析(2)经典排序算法对比

[TOC] 概述 上一篇文章分析了一下基本的排序算法以及Java的实现,不过没有比较深入的去分析,因为对于O(n^2)的算法实现比较简单,但是对于O(nLogn)的算法本身有些复杂,所以就分为两篇文章来...

wustor
2017/11/06
0
0
算法学习笔记(2)---插入排序

对于某个特定的场景,最快的排序算法可能与许多因素有关:例如关键值和卫星数据的先验知识,主机存储器的层次结构(高速缓存和虚拟存储)以及软件环境。 插入排序 插入排序对于少量待排元素还...

亭芳
2014/03/10
0
0
O(n*logn)级别的算法之二(快速排序)的三种实现方法详解及其与归并排序的对比

一,单路快排 1.测试用例: 1 #ifndef INC06QUICKSORTDEALWITHNEARLYORDEREDARRAYSORTTESTHELPERH 2 #define INC06QUICKSORTDEALWITHNEARLYORDEREDARRAYSORTTESTHELPERH 3 #include 4 #incl......

Tom-shushu
11/19
0
0
排序(上):冒泡排序、插入排序和选择排序

如何分析一个排序算法? 分析一个排序算法的三要素:排序算法的执行效率、排序算法的内存消耗以及排序算法的稳定性。 排序算法的执行效率 对于排序算法执行效率的分析,一般是从以下三个方面...

hardyyao
11/04
0
0
算法导论第二章小试牛刀

Author: bakari   Date: 2015.9.11 《算法导论》真是一本让人又爱又恨的书,爱自然是因为它精简凝练的算法呈现,读来让人欲罢不能;至于恨,是因为它在进行算法分析的时候所体现的数学思想...

chambai
2015/09/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Ubuntu16.04下安装docker

[TOC] 本文开发环境为Ubuntu 16.04 LTS 64位系统,通过apt的docker官方源安装最新的Docker CE(Community Edition),即Docker社区版,是开发人员和小型团队的理想选择。 1. 开始安装 1.1 由于...

豫华商
30分钟前
3
0
使用XShell工具密钥认证登录Linux系统

如果你是一名Linux运维,那么Linux服务器的系统安全问题,可能是你要考虑的,而系统登录方式有两种,密码和密钥。哪一种更加安全呢? 无疑是后者! 这里我为大家分享用Xshell利器使用密钥的方...

dragon_tech
42分钟前
1
0
day178-2018-12-15-英语流利阅读-待学习

“真蛛奶茶”了解一下?蜘蛛也会产奶了 Lala 2018-12-15 1.今日导读 “蛋白质含量是牛奶的 4 倍,并有着更低的脂肪和含糖量”,听起来诱人又美味的并不是羊奶或豆奶,而是你可能打死都想不到...

飞鱼说编程
47分钟前
9
0
npm WARN optional SKIPPING OPTIONAL DEPENDENCY: fsevents

场景重现 npm install --verbose 安装依赖的时,出现如下警告 强迫症患者表示不能接受 npm WARN optional SKIPPING OPTIONAL DEPENDENCY: fsevents@1.2.4 (node_modules\fsevents):npm WARN......

taadis
51分钟前
2
0
OSChina 周六乱弹 —— 你一口我一口多咬一口是小狗

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @达尔文 :分享Roy Orbison的单曲《She's a Mystery to Me》 《She's a Mystery to Me》- Roy Orbison 手机党少年们想听歌,请使劲儿戳(这里...

小小编辑
今天
363
6

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部