插入排序包括 直接插入排序, 折半插入排序, Shell排序
package com.longshine.arthmetic.sort; import java.util.ArrayList; import java.util.List; import com.longshine.arthmetic.NumSortElement; import com.longshine.arthmetic.SortElement; //直接插入排序 /** * 从第i项开始( 0<i<n)与第j项比较 0<=j<i; * 若i项 < j项, j+1项~ i-1项向后移动一位 * */ public class InsertSort { public static void main(String[] args){ int[] data = new int[] {5,8,1,20,15,13,7,6,30,45,3}; List<SortElement> lists = new ArrayList<SortElement>(); for (int d : data) { lists.add(new NumSortElement(d,"")); } lists.add(new NumSortElement(20,"*")); System.out.println(lists); new InsertSort().sort((List)lists); System.out.println(lists); } //开始排序 public void sort(List<NumSortElement> datas){ for(int i = 1; i < datas.size(); i++){ for(int j = 0; j < i; j++){ int c = datas.get(i).compareTo(datas.get(j)); if( c < 0){ //插入j位置 //j位置~i -1的位置元素向后移动1位 NumSortElement tmpI = datas.get(i); for(int k = i-1; k >= j; k--){ datas.set(k+1, datas.get(k)); } datas.set(j, tmpI); } else if(c==0){ //为了证明它是稳定排序 //插入j + 1位置 //j+1位置~ i -1的位置元素向后移动1位 NumSortElement tmpI = datas.get(i); for(int k = i-1; k >= j + 1; k--){ datas.set(k+1, datas.get(k)); } datas.set(j+1, tmpI); } } } } }
时间复杂度O(n2), 空间复杂度为O(1), 很好,没用上额外的空间
发表评论
-
java中断线程
2015-05-21 18:29 603Thread.stop方法可能中断线程,但不安全,此方法都 ... -
NIO下载服务器模拟实现(一)
2015-05-21 11:28 0从JDK 1.4开始,Java的标 ... -
java NIO教程
2015-05-18 10:39 0Java NIO提供了与标准IO ... -
Java反射,改变final属性
2015-05-16 16:58 523问: 怎么改变final属性? public cl ... -
Python实现的堆排序
2015-05-16 16:45 495堆排序属于选择排序,它其实就是一个建立大顶堆的过程 大顶 ... -
python 归并排序
2015-05-16 09:43 623排序思路: 1.将数组分成两组A,B,建立临时数组 C,C ... -
Python Shell排序
2015-05-11 16:29 565Shell排序属于插入排序, 增量为1的Shell排序就 ... -
Python折半插入排序
2015-05-11 12:44 1267折半插入排序是插入排序的一种,这是直接插入排序的改进,当将要为 ... -
Python版折半插入排序
2015-05-11 00:41 0import sort_element class H ... -
曾经的笔试题-- java Cloneable
2015-05-09 10:12 0public class CloneTest { ... -
一个公司的笔试题
2015-05-09 08:02 01.编程题,用两个线程实现对容量为10的队列的加入与取出. ... -
Shell排序
2014-03-26 17:01 0在 -
快速排序
2015-05-09 13:52 335快速排序使用分治法策略来把一个串行分为两个子串行。 步骤 ... -
java 虚拟机加载机制
2014-03-25 10:42 0虚拟机把描述类的数据从class文件加载到内存,并对数据进 ... -
java Class 类
2014-03-25 10:01 0Class对象 是用来创建类的常规对象的,当我们编译一个Ja ... -
成都网丁有限公司面试题
2014-03-24 16:44 0OO OO的原理 值传递与引用传递 ... -
自律编(一) java访问修饰符
2014-03-24 16:23 0一直以为java里只有三种访问修饰符 public, pr ... -
华莱公司笔试
2014-03-12 19:49 0public class Test { publi ... -
sleep与wait
2014-03-03 14:43 0Obj.wait(),与Obj.notify()必须要与syn ... -
线程、进程
2014-03-03 14:39 0线程:程序内部独立运行单位 线程与进程区别: 1 ...
相关推荐
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
用函数实现直接插入排序,并输出每趟排序的结果. Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出一趟排序结果,数据之间用一个空格分隔 Sample Input 10 ...
数据结构(c语言版)严蔚敏 吴伟民编著 中直接插入排序、折半排序、shell排序、冒泡排序、快速排序、选择排序、堆排序的实现、归并排序,使用c语言实现
直接插入排序 选择排序 堆排序 归并排序 快速排序 冒泡排序等七种排序方法
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
数据结构 综合排序 冒泡排序 直接插入排序 快速排序 希尔排序,完整的代码,有每种排序时间的比较
直接插入排序的四种实现代码, 见博客 直接插入排序(Straight Insertion Sorting)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有n-1个元素,排序...
插入排序之直接插入排序.cpp
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
提供8种排序算法中的直接插入排序,供大家学习参考
直接插入排序、希尔排序、冒泡排序、直接选择排序、堆排序、归并排序
数据结构---直接插入排序/快速排序/选择排序/冒泡排序(详细实现算法和性能比较)
试通过随机数据比较堆排序、直接插入排序算法的关键字比较次数和关键字移动次数。 (1)待排序表的表长不小于100;其中的数据要用伪随机数产生程序产生;至少要用5组不同的输入数据作比较;比较的指标为有关键字参加...
本实验含有四部分内容——直接插入排序、希尔排序、选择排序、快速排序,在上述内容的基础上,将所有排序算法整合在一个程序中。学生可参考教材中的伪代码。鼓励学生自创新思路,新算法。
直接插入排序法,是一个比较简单的排序法,比较基础,可供参考