文档章节

排序算法笔记:插入排序 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
码字总数 17135
作品 0
海淀
程序员
算法分析(2)经典排序算法对比

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

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

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

亭芳
2014/03/10
0
0
几种常见排序算法

几种常见排序算法 标签: algorithms [TOC] 本文介绍几种常见排序算法(选择排序,插入排序,希尔排序,归并排序,快速排序,堆排序),对算法的思路、性质、特点、具体步骤、java实现以及t...

brianway
2016/05/08
133
2
算法导论第二章小试牛刀

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

chambai
2015/09/11
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

[MicroPython]STM32F407开发板驱动OLED液晶屏

1.实验目的 1.学习在PC机系统中扩展简单I/O 接口的方法。 2.进一步学习编制数据输出程序的设计方法。 3.学习 F407 Micropython开发板控制OLED显示字符。 2.所需元器件 F407 Micropython开发板...

bodasisiter
23分钟前
0
0
php require和include 相对路径一个有趣的坑

以前总是被教育,不要使用相对路径,这样性能比较差,但是相对路径的问题不仅仅是性能哦,看下面这里例子 这是项目结构 .├── main.php├── t│ ├── t1.php│ └── t2.php└─...

anoty
23分钟前
13
0
x64技术之SSDT_Hook

测试环境: 虚拟机: Windows 7 64bit 过PG工具 驱动加载工具 PCHunter64 系统自带的计算器和任务管理器等 实现思路: 实际思路与win32的思路一样.都是替换SSDT表里边的函数地址.不过微软被搞怕...

simpower
24分钟前
0
0
TreeMap源码分析,看了都说好

一、简介 TreeMap最早出现在JDK 1.2中,是 Java 集合框架中比较重要一个的实现。TreeMap 底层基于红黑树实现,可保证在log(n)时间复杂度内完成 containsKey、get、put 和 remove 操作,效率很...

Java小铺
34分钟前
0
0
协变、逆变

概念 假设 A、B表示类型 ≤ 表示继承关系 f<⋅>表示类型转换 若A ≤ B,则 A是B的子类,B是A的超类 协变、逆变 什么是型变?型变(type variance)允许对类型进行子类型转换。 为了下面讲解先...

obaniu
40分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部