儿时的编程算法心得笔记

作者：火鸟 redbirdli@hotmail.com

火鸟编程追求小、快、精，所以算法问题成为了我不断学习和探索的方向，现将一些心得贴出，供诸位高手批评指正，也望能有些抛砖引玉的裨益。先来看看火鸟在注册表研究中的发现(此处为过去进行时，时间约为1999-2000年之间)。

隐藏驱动器算法 a..z 用 2的n次方表示如隐藏a和c 用2的0次+2的2次=5表示
var stmp:string;
itmp,irun,ival:integer;
begin
ival:=0;
stmp:=uppercase(edit1.text);
for irun:=1 to length(stmp) do
begin
itmp:=ord(stmp[irun])-66;
itmp:=Trunc(Ldexp(2,itmp));
ival:=ival+itmp;
end;
edit2.text:=inttostr(ival);
//以上是正向运算
stmp:='';
while ival >0 do
begin
for irun:=0 to 25 do if Ldexp(2,irun)>ival then break;
ival:=ival-Trunc(Ldexp(2,irun-1));
stmp:=chr(65+irun)+stmp;
end;
edit3.Text :=stmp;

点评：此法似乎无太大用途，因为其虽将各字母用同一字符表示，但有以下不足：1.字母在字串中必须唯一，即不能第二次出现同一个字母；2.返回的字符无法确定原来的排列次序。鸡肋是也！火鸟倒是想到了此法的一个用处，如您正在做一个管理系统的权限模块，可以用I、O、Q、B、M等字母表示其进货、销售、查询、数据备份和管理员维护等功能。将其经过算法处理后写入同一个字段，一来可以加密权限操作，二来可以减小字段长度。如将其转换成16进制或更高进制（火鸟建议您将16以后的数字按F代表16的概念顺序排下去）您的字段将更小也将更安全。

以下是关于运算速度的问题，先声明，火鸟本学不是计算机，所以如您觉得这些问题是课本上早讲过的。不必见笑，跳过不看便是。以下是代码：

procedure TForm1.Button1Click(Sender: TObject);//这是一个使用了指针的排序
var it:array[0..39999] of integer;
itmp,irun,iset:integer;
pi:^integer;
begin
for itmp:=0 to 39999 do
it[itmp]:=39999-itmp+Random(999);
caption:=timetostr(time)+'-'; //开始计时
for itmp:=0 to 39999 do
begin
pi:=@it[itmp];
for irun:=itmp+1 to 39999 do
if pi^>it[irun] then pi:=@it[irun];
iset:=it[itmp];
it[itmp]:=pi^;
pi^:=iset;
end;
caption:=caption+timetostr(time);//计时结束，在火鸟P3 533EB 128M内存中运算了7秒左右
end;

procedure TForm1.Button1Click(Sender: TObject);//这是一个未使用指针的排序
var it:array[0..39999] of integer;
itmp,irun,iset:integer;
pi:integer;
begin
for itmp:=0 to 39999 do
it[itmp]:=39999-itmp+Random(999);
caption:=timetostr(time)+'-'; //开始计时
for itmp:=0 to 39999 do
begin
pi:=itmp;
for irun:=itmp+1 to 39999 do
if it[pi]>it[irun] then pi:=irun;
iset:=it[itmp];
it[itmp]:=it[pi];
it[pi]:=iset;
end;
caption:=caption+timetostr(time);//在同样环境中运算了10秒以上
end;
点评：以上两种算法唯一不同之处在于，第一种在循环中运行了指针，而第二种在循环中直接对值操作,可见运用指针可以提高程序效率。

procedure TForm1.Button1Click(Sender: TObject);//这是一个插入排序法
var it:array[0..39999] of integer;
itmp,irun,iset:integer;
pi:integer;
begin
for itmp:=0 to 39999 do
it[itmp]:=39999-itmp+Random(999);
caption:=timetostr(time)+'-'; //开始计时
for itmp:=1 to 39999 do
begin
pi:=it[itmp];
irun:=itmp-1;
while (pi< it[irun]) and (irun>-1) do
begin
it[irun+1]:=it[irun];
irun:=irun-1;
end;
it[irun+1]:=pi;
end;
caption:=caption+timetostr(time);//在同样环境中运算了6-7秒
end;

如您已读懂了以上的插入排序法的代码，再来看看老美Shell早在1959年（玩笑话：好像那时我妈妈还在上托儿所）提出的插入排序法，此法也称为减小步长法：
procedure TForm1.Button1Click(Sender: TObject);
var it:array[0..39999] of integer;
itmp,irun,iset:integer;
pi:integer;
begin
for itmp:=0 to 39999 do
it[itmp]:=39999-itmp+Random(999);
caption:=timetostr(time)+'-'; //开始计时
iset:=40000;
while iset>1 do
begin
iset:=iset div 2;
itmp:=iset;
repeat
pi:=it[itmp];
irun:=itmp-iset;
while (irun>-1) and (pi< it[irun]) do
begin
it[irun+iset]:=it[irun];
irun:=irun-iset;
end;
it[irun+iset]:=pi;
itmp:=itmp+1;
until itmp>40000
end;
caption:=caption+timetostr(time);//在同样环境中运算不到1秒!即使将数组扩大到199999，仍然能在一秒中内完成！

end;

点评：火鸟以前只会用所谓“冒泡法”排序，见了Shell 真不愧为醍醐灌顶，大梦方醒。真是精巧的算法！套一句广告词“不只是快一点”你也来试试吧！

作者：火鸟 redbirdli@hotmail.com