Java排序方法之：插入排序

我个人理解的插入排序算法：
      从前往后遍历一个数组，第二个元素开始，每个元素都在当前位置从后往前依次比较，如果前面的元素比这个元素大，则前面的元素后移一位。这样，第二个元素起，每个元素处最多可能要移动n-1次，n是当前元素的序号（起始序号是1），当前元素处比较一轮后，这个位置之前已经是升序了。

 

InsertSort.java

//package com.liany.demo.sort;

import java.util.Arrays;

public class InsertSort {
	
	public static void sort(int[] array){
		int first = 0;
		int last = array.length-1;
		
		for(int i = first+1; i <= last; i++){
			int temp = array[i];
			int j = i-1;
			
			while(j>=first && temp<array[j]){
				array[j+1]=array[j];
				j--;
			}
			
			array[j+1] = temp;
			//打印这一轮的排序结果
			System.out.println(Arrays.toString(array)); 
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] array = {10,3,1,4,9,8,7,5,6,};
		sort(array);
	}
}

 

程序打印结果：

[3, 10, 1, 4, 9, 8, 7, 5, 6]
[1, 3, 10, 4, 9, 8, 7, 5, 6]
[1, 3, 4, 10, 9, 8, 7, 5, 6]
[1, 3, 4, 9, 10, 8, 7, 5, 6]
[1, 3, 4, 8, 9, 10, 7, 5, 6]
[1, 3, 4, 7, 8, 9, 10, 5, 6]
[1, 3, 4, 5, 7, 8, 9, 10, 6]
[1, 3, 4, 5, 6, 7, 8, 9, 10]

 

参考了以下博客hualang：http://www.iteye.com/topic/1116236