算法基础

一.插入排序

​ 和打扑克牌的排序算法相同，依次从桌子上拿扑克牌放到手上，放到手上时需要放在手上牌堆的正确位置。

1
2
3
4
5
6
7
8
9
INSERTION-SORT(A):
	for j = 2 to A.length
		key = A[j]
		//将key插入到已排序列的正确位置
		i = j - 1
		while i > 0 and A[i] > key
			A[i+1] = A[i]
			i = i - 1
		A[i+1] = key

简要分析: 第2行单次需要常数c1c_1的时间，设循环nn次，则第3、5行单次分别为c2,c3c_2,c_3，循环n−1n-1次，这是因为for循环不满足条件后不再进入循环体。第6行单次c4c_4，循环次数为∑j=2ntj\sum _{j=2}^nt_j，tjt_j代表第jj次for循环时，while循环执行的次数，这取决于数据的具体情况。7、8行与3、5行类似，需要减1，第9行和第3、5行的次数相同。

总次数

T(n)=c1n+c2(n−1)+c3(n−1)+c4∑j=2ntj+c5∑j=2n(tj−1)+c6∑j=2n(tj−1)+c7(n−1)T(n)=c_1n+c_2(n-1)+c_3(n-1)+c_4\sum_{j=2}^nt_j+\\\\ c_5\sum_{j=2}^n(t_j-1)+c_6\sum_{j=2}^n(t_j-1)+c_7(n-1)

当每一次新插入的元素比有序序列的最后一个元素还大，也就是排序前整个待排序列就已经是从小到大的有序序列时，相当于每次的新扑克牌直接放在最后的位置，此时tj=1t_j=1，while循环只进行1次，T(n)=c1n+c2(n−1)+c3(n−1)+c4(n−1)+c7(n−1)T(n)=c_1n+c_2(n-1)+c_3(n-1)+c_4(n-1)+c_7(n-1)，因此是线性函数。而当完全倒序的时候，tj=jt_j=j，此时新扑克牌要一直向前比较到第一张，因此求和式是等差数列的和，是二次的。平均情况下，每次新的扑克牌要放到排好的扑克牌中间，tj≈j2t_j\approx\frac{j}{2}，此时仍然是等差数列求和是二次的。

二.归并排序

​ 将n个元素的数组排列好需要先将左半部分和右半部分分别排好，然后在两组排好的序列中分别添加游标，将左游标和右游标比较，将较小的那个存入最终序列，然后移动该游标继续与另一个游标的值比较。对于左半部分和右半部分也需要递归地用这种方法排好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
MERGE(A, p, q, r)://p到q为有序的左半部分，q+1到r为有序的右半部分
	n1 = q - p + 1	//左半部分元素个数
	n2 = r - q	//右半部分元素个数
	let L[1..n1+1] and R[1..n2+1] be new arrays
	for i = 1 to n1
		L[i] = A[p+i-1] //提取左半部分存入
	for j = 1 to n2
		R[j] = A[q+j]	//提取右半部分存入
	L[n1+1] = INF	//为后面归并排序的递归出口做准备
	R[n2+1] = INF
	i = 1
	j = 1
	for k = p to r	//将左半部分和右半部分合并
		if L[i] <= R[j]
			A[k] = L[i]
			i = i + 1
		else A[k] = R[j]
			j = j + 1

1
2
3
4
5
6
MERGE-SORT(A, p, r):
	if p < r
		q = (p + r) / 2
		MERGE-SORT(A, p, q)	//排左半部分
		MERGE-SORT(A, q+1, r)	//排右半部分
		MERGE(A, p, q, r)	//将左半部分和右半部分合并

简要分析: 设总时间为T(n)T(n)，则总时间包括排左半部分和右半部分的时间和加上合并的时间(单层循环是线性时间)，因此可以得到

T(n)={c,n=12T(n/2)+cn,n>1T(n)=\begin{cases} c,n=1 \\\\ 2T(n/2)+cn,n>1 \end{cases}

图解

总代价是线性函数乘对数函数。