当前位置:首页 > 开发 > 软件应用 > 正文

第四课 插入排序

发表于: 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

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号