当前位置:首页 > 开发 > 行业应用 > 正文

第四课 插入排序

发表于: 2010-03-30   作者:飞雪无情   来源:转载   浏览次数:
摘要: 引用笔记--插入排序1.插入排序类 packagecom.flysnow.chap03; /** *插入排序 *@author飞雪无情 *@since:2010-3-25 */ publicclassArrayInsert{ privatelong[]a; privateintnElems; publicArrayInsert(intmax){ a=newlong[max
引用
笔记--插入排序

1.插入排序类
package com.flysnow.chap03;

/**
 * 插入排序
 * @author 飞雪无情
 * @since:2010-3-25
 */
public class ArrayInsert {
	private long[] a;
	private int nElems;
	public ArrayInsert(int max){
		a=new long[max];
		nElems=0;
	}
	/**
	 * 插入元素
	 * @param value
	 */
	public void insert(long value){
		a[nElems]=value;
		nElems++;
	}
	/**
	 * 打印元素
	 */
	public void display(){
		for(int i=0;i<nElems;i++){
			System.out.print(a[i]+" ");
		}
		System.out.println();
	}
	/**
	 * 插入排序排序
	 */
	public void insertionSort(){//比较次数O(N^2),但是复制比交换的时间要少。比冒泡快一倍,比插入略快
		int out,in;
		for(out=0;out<nElems;out++){
			long temp=a[out];//标记
			in=out;
			while(in>0&&a[in-1]>=temp){//大于标记值右移 
				a[in]=a[in-1];
				--in;
			}
			a[in]=temp;
		}
	}
}


2.插入排序测试
package com.flysnow.chap03;

import java.util.Random;

/**
 * 插入排序测试
 * @author 飞雪无情
 * @since:2010-3-25
 */
public class InsertSortApp {
	public static void main(String[] args){
		ArrayInsert insert=new ArrayInsert(100);
		Random random=new Random();
		for(int i=0;i<20;i++){//添加20个随机数
			insert.insert((long)(random.nextFloat()*100));
		}
		insert.display();//未排序
		insert.insertionSort();//排序
		insert.display();//排序后
	}
}

3.总结
算法思想:
  • 选择第二个(1号)数据为标记,和其前面的数据(0号)比较,如果1号数据小于0,则0号后移变成1号,而原来的1号数据占据原来的0号位置。
  • 选择第三个(2号)数据位标记,和其前面的数据(0号,1号)循环比较,如果前面的数据比标记大,则该数据后移。
  • 依次类推,直到完成排序。。循环条件就是下标大于0并且前面的数据大于等于标记值。


第四课 插入排序_第1张图片

第四课 插入排序_第2张图片

第四课 插入排序

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
引用 笔记--插入排序 1.插入排序类 package com.flysnow.chap03; /** * 插入排序 * @author 飞雪无
引用 笔记--插入排序 1.插入排序类 package com.flysnow.chap03; /** * 插入排序 * @author 飞雪无
上一课中我教给您三角形和四边形的着色。这一课我将教您如何将这些彩色对象绕着坐标轴旋转。 其实只
插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕。
插入排序: 包括:直接插入排序,二分插入排序(又称折半插入排序),链表插入排序,希尔排序(又称
. package sortAlgorithem; import java.util.Arrays; /** * 参考:http://v.youku.com/v_show/id_XM
插入排序的思想: 插入排序算法与我们打牌时,排列牌的顺序差不多。在我们摸牌时,我们一次一张牌的
插入排序 Insertion Sort 插入排序的基本思想是,经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅
基本思想 经典排序算法 – 插入排序Insertion sort 插入排序就是每一步都将一个待排数据按其大小插
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号