插入排序算法

定义：将待排序数据按照排序规则插入到已排序的数据中。
条件：数据为已排序。

场景：少量数据下使用
时间：O(n2)
图解：

?实现：

    int[] sort = {9,7,2,4,6,1,3,8,5};
		//初始时认为sort中0位的数据为排好序的数据，分别对1至8位的数据进行插入 
		for(int i=1;i<sort.length;i++){
			//将待插入数据赋值给key
			int key = sort[i];
			//将j位的数据后移一位
			int j = i-1;
			//对数据从后往前进行遍历，将数据后移一位，直到到达排序数据的最前面或者key值大于数据
			while(j>=0&&sort[j]>key){
				//数据后移
				sort[j+1]=sort[j];
				//j前移一位
				j=j-1;
			}
			//把key值插入
			sort[j+1] = key;
		}

?
? 分析：

int[] sort = {9,7,2,4,6,1,3,8,5};                   时间          次数
for(int i=1;i<sort.length;i++){                      c1            n
	int key = sort[i];                           c2            n-1
	int j = i-1;                                 c3            n-1
	while(j>=0&&sort[j]>key){                    c4            ∑tj j=1...n
	     sort[j+1]=sort[j];                      c5            ∑(tj-1) j=1...n
	     j=j-1;                                  c6            ∑(tj-1) j=1...n
	}
	sort[j+1] = key;                             c7            n-1
}

?
1、最佳情况：
? ? ?c4*∑tj + c5*∑(tj-1) + c6*∑(tj-1) 执行n-1次完成? 即 c4*(n-1)
? ? ?T(n) = c1*n + c2*(n-1) + c3*(n-1) + c4*(n-1) + c7(n-1)
? ? ? ? ? ? ?= c1*n + c2*n - c2 + c3n - c3 + c4n - c4 + c7n - c7
? ? ? ? ? ? ?= (c1 + c2 + c3 + c4 + c7)n - (c2 + c3 + c4 + c7)
? ? ? ? ? ? 是an+b 时间维度为：O(n)

2、最差情况：
? ? ? ∑tj = n*(n+1)/2????? j=1.....n
? ? ? ∑(tj-1) = n*(n-1)/2? j=1.....n
? ? ? T(n) = c1*n + c2*(n-1) + c3*(n-1) + c4*n*(n+1)/2 + c5*n*(n-1)/2 + c6*n*(n-1)/2 + c7(n-1)
? ? ? ? ? ? ?= c1n + c2n - c2 + c3n - c3 + c4n^2*(1/2) + c4n/2 + c5n^2*(1/2)
? ? ? ? ? ? ? ? - c5n/2 + c6n^2 -c6n/2 + c7n - c7
? ? ? ? ? ? ?= (c4/2+c5/2+c6/2)n^2 + (c1-c2-c3+c4/2-c5/2-c6/2+c7)n - (c2+c3+c7)
? ? ? ? ? ? ?是an^2+bn+c 时间维度为：O(n^2)

?

插入排序算法

原文：http://maxiaofeng1982.iteye.com/blog/2276934