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