1.算法正确性的证明
数学归纳法：
证明当 n = 1 时命题成立。证明如果在 n = m 时命题成立，那么可以推导 出在 n = m +1 时命题也成立。（m 代表任意自然数）算法的迭代性，以及有类似归纳法的特性可以用归纳法来证明其正确性。
2.插入算法。
效率：
/******************************************************************** *best Θ (n ) *hard Θ (n 2 ) **********************************************************************/
伪代码：
INSERTION-SORT(A) cost times 1 for j ← 2 to length[A] c1 n 2 do key ← A[j] c2 n - 1 3 ▹ Insert A[j] into the sorted sequence A[1 ‥ j - 1]. 0 n - 1 4 i ← j - 1 c4 n - 1 5 while i > 0 and A[i] > key c5 6 do A[i + 1] ← A[i] c6 7 i ← i - 1 c7 8 A[i + 1] ← key c8 n - 1 C语言实现： /******************************************************************** *best o(n) *hard o(n2) **********************************************************************/ void insert_sort_algorthms(char* T) { int j,i =0; int len,key = 0; len = strlen(T); i =0; for(j=1;j<len;j++) { key = T[j]; i =j-1; while(i>=0 &&T[i]>key) { T[i+1] = T[i]; i = i-1; T[i+1] = key; } } }