算法导论第2章(1)：插入排序,算法分析
排序基类
public abstract class Sort{public static final int INCREMENT = 0; //升序public static final int DECREMENT = 0; //降序/** * 排序过程 * @param s 带排数列 * @param incOrDec 控制升序还是降序 * @return */public int [] sort(int [] s, int incOrDec){return null;};/** * 打印 一个数列 * @param s */public void print(int [] s){if(s == null) { System.out.println("s == null"); return; }for(int i:s)System.out.print(i +" ");}}
对数列A进行排序
伪代码：1
for j <- 2 to length(A)
2
do key <-A[j]
3
// 把A[j]插入到已经排好序的数列A[1...j-1]中
4
i <- j-1;
5
//已经排好序的数列A[1...j-1]中中，找到第一个比key小的元素的位置
6
while i>0 and A[i] > key
7
do A[i+1]<-A[i]
8
i <- i-1
9
A[i+1] = key;
下面是一个例子的排序过程：
/** * * @author buptjunjun * @time 2013-1-22 * */public class InsertSort extends Sort{/** * 插入排序 * @param s 带排数列 * @param incOrDec 控制升序还是降序 * @return */@Override public int[] sort(int[] s,int incOrDec) {if(s == null || s.length <=1) return s;for(int i = 1;i <s.length; i++){int key = s[i];int j = i-1;//下面将key插入到已经排好的数列中去if(incOrDec == Sort.INCREMENT) //升序{while(j>=0 && key<s[j]){ s[j+1] = s[j]; j--;}}else if(incOrDec == Sort.DECREMENT) //降序{while(j>=0 && key>s[j]){ s[j+1] = s[j]; j--;}}s[j+1] = key;}return s;}/** * @param args */public static void main(String[] args){int [] s = {2,5,3,1,1,3,4,4,9,0};int [] ret = new InsertSort().sort(s,Sort.INCREMENT);new InsertSort().print(s);}}要证明一个算法是正确的，分２步：
１、在第一轮迭代之前是正确的
２、在循环的某一次迭代开始之前是正确的，在下一次开始之前是正确的。
其实这就是一个数学归纳法的应用
算法分析
Num
算法
Cost
T
1
for j <- 2 to length(A)
C1
n
2
do key <-A[j]
C2
n-1
3
// 把A[j]插入到已经排好序的数列A[1...j-1]中
0
n-1
4
i <- j-1;
C3
n-1
5
//已经排好序的数列A[1...j-1]中中，找到第一个比key小的元素的位置
0
n-1
6
while i>0 and A[i] > key
C4
7
do A[i+1]<-A[i]
C5
8
i <- i-1
C6
9
A[i+1] = key;
C7
n-1
其中Ci是第j个语句的所用时间，Tj是j个语句执行的次数
总时间就是：
T = n*C1 + (n-1)*C2+ (n-1)*C3+ ()*C4 + () *C5+ () *C6+(n-1)*C7
现在要确定的是tj
当数组已经是排好序的那么tj= 1
T = n*C1 + (n-1)*C2+ (n-1)*C3+ (n-1)*C4+ +(n-1)*C7
= (C1+C2+C3+C4+C7)n -(C2+C3+C4+C7) = a*n+b
可见当值排好序的情况下 T是n的线性函数
当数组已经是按逆序排好序的那么tj= j
T = n*C1 + (n-1)*C2+ (n-1)*C3+ ()*C4 + () *C5+ () *C6+(n-1)*C7
=a*n2+b*n+c
可见 T是关于n的二次函数
函数增长量级：
在前面分析中，我们忽略了每条语句的真实代价，使用a b c来代替，他们是依赖于Cj的。可以再做抽象，我们取最高次项，忽略了低次项目，因为当n很大的时候低次项是不重要的。
可以进一步抽象去掉最高次项的系数，因为因为当n很大的时候，系数对增长率的贡献很小。
这样可以这样表示插入排序的最坏时间代价为 