前些天便开始读T.H Cormen等著的<<算法导论>>,希望能在数据结构课程结束后,对基本DS及算法设计分析基础有更加深入的了解.
今天从MIT的开放课程计划中顺利找到了<<ITA>>,MIT给出的教学计划囊括了排序,递归,树,图结构,以及NP问题分析.我打算选取本书中较为重要同时有浓厚兴趣,特别是数学分析部分来学习.下载了MIT教学讲义,浏览起来很象国内使用的PPT教学,整个教学言简意赅,同时不失风趣幽默.
今天用C首先实现了插入排序和合并排序,具体代码为:
对于插入排序,除理解时间复杂度的计算以外,我特别留意在比较交换部分的代码实现:
/* 插入排序算法的实现 */#include <stdio.h>void InsertionSort(int A[]) {int j,i,key; for(j=1;j<=5;j++) { key=A[j]; for(i=j-1;i>=0;i--) if(key>=A[i]) break; else A[i+1]=A[i]; A[i+1]=key; } }
void main(){ int n; int AB[6]={5,2,4,6,1,3}; InsertionSort(AB); for(n=0;n<=5;n++) printf("%d",AB[n]); getch();}
while(A[i]>0 AND A[i]>A[j]) -------------1
do A[i+1]=A[i]---------------2
i=i-1;------------------3
A[i+1]=key;-------------4
第1句限定进入比较的条件,无可非议;第2句即当j所在数值小于其前一数值,将两值交换,交换后A[I]的值顺利到位,J值随被替换但KEY中仍为保留;第3句,为寻找数值的最后确定位置作出的步减.第四句,在有必要交换时,能重新安排J值,不需交换时,即A[j]=key.妙哉!
