【算法】排序算法之插入排序

插入排序是最简单的排序算法之一。插入排序由N-1趟排序组成。

算法：

算法核心 是实现 当前位置之前比当前数大的数依次向右移动。

/**
	 * @param a[]
	 */
	public static void insertionSort(int [] a){
		
		int j;
		for (int i = 1; i < a.length; i++) {
			int tmp=a[i];
			for (j=i; j>0&&tmp<a[j-1];j--) {
				a[j]=a[j-1];
			}
			a[j]=tmp;
		}
	}

　　

第二层循环的目的是将比当前数大的值向右移动，从而将合适的位置空出来存放当前值。

分析：

嵌套循环每一次迭代花费N次迭代，因此插入排序为O(N²),而且界是精确的，以反序的顺序输入即可达到该界。

内循环中元素的比较次数对于i的每个值最多是i+1次。

如果输入几乎被排序，那么运行时间为O(N).

来自为知笔记(Wiz)