插入排序

插入排序（InsertionSort）是一个对少量元素进行排序的有效算法，它的基本思想和打牌时整理牌的顺序方法类似：如果右手中有一组需要按照大小排序的牌，则依次从中取出一张牌放入左手，每次新取出的牌按照大小关系插入到左手牌中合适的位置，直到所有的牌都排序完成，因此称之为插入排序。

插入排序的Java代码如下所示：

[code lang=”java”]public class InsertionSort{ public static int[] sort(int[] array){ for(int i = 1; i < array.length; i++){
int key = array[i];
int j = i - 1; while(j >= 0 & array[j] > key) { array[j+1] = array[j]; j–; } array[j+1] = key; } return array; }

public static void main(String[] args){
	int[] array = {3, 2, 6, 1, 9, 7, 8, 5, 4};
	for(int i : array){
		System.out.print(i + ",");
	}
	System.out.print("\n");
	array = sort(array);
	for(int i : array){
		System.out.print(i + ",");
	}
} }[/code]

在最优情况下，即待排序数的顺序已经排好，则上面算法中，插入部分（while循环）不需要进行，插入排序的算法复杂度是O(n）；在最坏情况下，待排序数是逆序的，插入部分需要进行最多次，则算法复杂度是O(n^2）。

总结：插入排序对部分有序的数据是极好的排序算法，对小型数据也是较好的排序方法。