直接插入排序

package com.arithmetic;

import java.util.Random;

/**
 * 直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，
 * 直到全部记录插入完成为止。
 * @author xugang
 */
public class Insertsort {
	
	public static void insertSort( int[] arr ){
		for (int i = 1; i < arr.length; i++) {
			insert( arr, i );
		}
	}
	
	//把arr[i]插入到i之前的有序队列中。
	private static void insert(int[] arr,  int i) {
		int f = -1 ;
		int temp = arr[i];
		for (int j = 0; j < i ; j++) {
			if( arr[i] < arr[j] ){
				f = j ;
				break;
			}
		}
		if(f==-1) return ;
		for( int k = i-1 ; k >= f ; k-- ){
			arr[k+1] = arr[k];
		}
		arr[f] = temp ;
	}
	
	
	public static void main(String[] args) {
		Random random = new Random();
		int size = 20 ;
		int[] r = new int[size];
		for (int i = 0; i < r.length; i++) {
			r[i] = Math.abs(random.nextInt())%200 ; 
		}
		long l1 = System.currentTimeMillis();
		insertSort(r);
		long l2 = System.currentTimeMillis();
		System.out.println( "消耗=" + (l2 - l1) ) ;
		for (int i = 0; i < r.length; i++) {
			System.out.println(r[i]);
		}
	}
	
}