java排序3（插入排序）

package hello;

import java.util.Random;
/**
 *插入排序:
 * 需要时间O(N*N),但是在一般情况下,要比冒泡排序快一倍,也比选择排序快
 * 它经常用在较复杂排序算法的最后阶段,例如快速排序
 * 局部有序,再进行插入比较
 * 
 * 但是:对于逆序排序的数据,每次比较和移动都会执行,所以这样并不比冒泡排序快.
 * 
 * 不变性:
 */
public class InsertSortApp {
	
	public static void main(String[] args) {
		long ls = System.currentTimeMillis();
		
		int maxSize = 10000;
		InsertSort arr;
		arr = new InsertSort(maxSize);
		Random r = new Random();
		//insert 10 items
		for(int i=0;i<10000;i++){
			arr.insert(r.nextInt(100));
		}
		arr.display();
		arr.insertionSort();
		arr.display();
		
		System.out.println(System.currentTimeMillis()-ls);
	}
}

class InsertSort extends BubbleSort{
	
	public InsertSort(int max) {
		super(max);
	}
	
	/**
	 * 在外层的for循环中,out变量从1开始,向右移动.
	 * 他标记了未排序部分的最左端的数据.
	 * 内层的while循环中,in的变量从out开始,向左移动,
	 * 直到temp变量小于in所指的数组数据项,或者它已经不能左移为止.
	 * while循环的每一趟都向右移动了一个已经排好序的数据项.
	 * 
	 */
	public void insertionSort(){
		int in,out;
		for(out=1;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;
		}
	}
}