简单插入排序.c

void SimpleSort(RecType r[],int N){//存放无序记录数组，数组的长度
    int i,j;
    for(i=2;i<=N;i++){
        r[0]=r[i];//第一次未使用监视哨，不能写成r[0].key=r[i].key!!!
        j=i-1;
        while(r[j].key>r[i].key){//r【i】前面的元素不能比它本身大
            r[j+1]=r[j];//边寻找边空出位置，写成了r【j】=r[j+1]!!!!
            j--;
        }
        //执行完毕，插入位置的元素已经到达了他的后面
        //而且j又跑到了插入位置的前面
        r[j+1]=r[0];
    }
}
//算法分析：
//1.最好的情况 已经递增有序
//     比较：i=2 j前面1个元素比较2...i=n 前面有n-1个元素 比较n次  2+3+4...+n   O(n2)
//     交换：总共n-1个循环 每个循环（1次更新哨兵 跟新完成又将哨兵复制到原位置）O(2(n-1))=O(n)
//2.最坏的情况：
 //    比较：i=2 j前面1个元素比较2...i=n 前面有n-1个元素 比较n次  2+3+4...+n   O(n2)
 //    交换：每一轮循环都复制两次 移动i-1次                                    O(n2)


 //3.平均移动次数 O（n2）
 //  平均比较次数O（n2）