插入排序

.

package sortAlgorithem;

import java.util.Arrays;

/**
 * 参考：http://v.youku.com/v_show/id_XMjIyMjgzNTMy.html
 * 
 * 改进：将嵌套的两个for循环写成了两个方法，这样逻辑更清晰
 * 
 * @author [e-mail] @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;
	}
}

输出结果：

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