package com.itjob.algorithm;

public class InsertSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] array = {2, 5, 3, 1, 9, 8, 10};
		insertSort(array);
		for (int i = 0; i < array.length; i++)
		{
			System.out.println(array[i]);
		}
	}

	/**
	 * 插入排序算法
	 * @param array
	 */
	static void insertSort(int[] array) {
		int in, out, len;
		len = array.length;
		// 外循环是给每个数据循环
		for (out = 1; out < len; out++) {
			// 先取出来保存到临时变量里
			int temp = array[out];
			// in是记录插入数据之前的每个数据下标
			in = out;
			// while内循环是找插入数据的位置，并且把该位置之后的数据（包括该位置）
			// 依次往后顺移。
			while (in > 0 && array[in - 1] >= temp) {
				// 往后顺移
				array[in] = array[in - 1];
				// 继续往前搜索
				--in;
			}

			// 该数据要插入的位置
			array[in] = temp;
		}
	}
}
