插入排序--直接插入排序

直接插入排序

算法实现

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
给出Java代码如下

	public void insertSort(int[] a) {
		for (int i = 1; i < a.length; i++) {
			int key = a[i];
			for (int j = i - 1; j >= 0 && a[j] > key; j--) {
				a[j + 1] = a[j];
				a[j] = key;
			}
		}
	}

分析

最坏情况下进行n*(n-1)次计算，时间复杂度为O(n2)。因此插入排序不适用于数据量比较大时候的排序。如果需要排序的数据量较小，那么插入排序还是一个不错的。