算法导论 插入排序

输入： n个数<a1, a2, ..., an>

输出：输入序列的一个排列（即重新排序）<a1', a2', ..., an'>，使得a1' <= a2' <= ... <= an'

 

伪代码就不在赘述，详细见算法导论书第二版

用java代码实现如下

public class InsertionSort {
	public static void insert(Integer[] input) {
		for(int i = 1; i < input.length; i ++) {
			int current = input[i];
			//把current插入到input[0...i-1]中
			int j = i - 1;
			while((j >= 0) && input[j] > current ) {
				input[j + 1] = input[j];
				j = j -1;
			}
			input[j + 1] = current;
		}
		
		for(int i = 0; i < input.length; i ++) {
			System.out.println(input[i] + ", ");
		}
	}
	public static void main(String[] args) {
		Integer[] input = new Integer[]{
			3,5,7,1,6,9,4,2,8
		};
		insert(input);
	}
}

 

 算法复杂度：O(n2)