.


[img]http://dl.iteye.com/upload/picture/pic/89090/d7639744-af5c-339c-9f2c-a13e2ef54f84.jpg[/img]




package sortAlgorithem;

import java.util.Arrays;

/**
* 参考：http://v.youku.com/v_show/id_XMjIyMjgzNTMy.html
*
* 改进：将嵌套的两个for循环写成了两个方法，这样逻辑更清晰
*
* @author ocaicai@yeah.net @date: 2011-5-2
*
*/
public class InsertionSort {

/**
* @param args
*/
public static void main(String[] args) {
int[] targetArray = { 1, 2, 66, 33, 6, 4, 6, 9, 0, 12 };
System.out.println("原数组：" + Arrays.toString(targetArray));
System.out.println("排序后：" + Arrays.toString(insertAll(targetArray)));
}

private static int[] insertAll(int[] array) {
// 默认只有一个数字时是有序的，即是只有0位置是有序的所以从第index=1开始
for (int index = 1; index < array.length; index++) {
insertOnce(array, index);
}
return array;
}

private static void insertOnce(int[] array, int highIndex) {
// 临时记录最高的这个值
int hightIndexValue = array[highIndex];
// 在低区从高到低依次查看比较
// 把index写在for外面主要是构成一个方法内范围的变量而不仅仅是for内的
int index = highIndex - 1;
for (; index >= 0 && hightIndexValue < array[index]; index--) {
// 每往低处走一步即index--一次就把低处的值赋值给相邻的高处的索引
array[index + 1] = array[index];
}
// 将条件中的index--那一次加回来
array[index + 1] = hightIndexValue;
}
}




[color=red]输出结果：[/color]



原数组：[1, 2, 66, 33, 6, 4, 6, 9, 0, 12]
排序后：[66, 33, 12, 9, 6, 6, 4, 2, 1, 0]