希尔法排序.doc

希尔法排序
1、输入n个数到a(n)，用希尔法对a(n)进行从大到小的排序。
算法：
(1)建立数组a(n)
(2)取初始增量d=int(n/2);
(3)从第一个数开始，把相隔为d的数分为一组，对每一组用插入法排序
(4)取增量为上一个增量的一半d=int(d/2);
(5)判断:若d＝0则完成排序，输出结果；否则转(3)。
CLS
DATA48,36,65,99,74,42,48,31,92,5
INPUT"n=";n
DIMa(n)
FORi=1TOn:READa(i):NEXTi
PRINT"paixuqian:";
FORi=:NEXTi:PRINT
d=INT(n/2)
WHILEd>=1
FORi=d+1TOnSTEPd
a(0)=a(i):j=i-d
WHILEa(0)<a(j)
a(j+d)=a(j):j=j-d
IFj<=0THENk=j:j=0
WEND
IFj=0THENj=k
a(j+d)=a(0)
NEXTi
d=INT(d/2)
WEND
PRINT"paixuhou:";
FORi=:NEXTi
END

计数法排序:
2、编程:从键盘输入任意一个三十位以内的正整数、然后将组成这个数的各个数字重新排列，得到一个最小数，将这个数打印出来。
算法分析:由于输入的是三十位以内的正整数，只能用字符串存放，最直接最简单的思路是:取出字符串的每一个数存放到数组中，在保证第一位数是非零的情况将数组元素从小到大输出。
CLS
DIMa(9)
DO
flag1=0:flag2=0
INPUT"x$=";x$:l=LEN(x$)
IFl>30THENflag1=1
FORi=1TOl
y$=MID$(x$,i,1)
IFy$<"0"ORy$>"9"THENflag2=1
NEXTi
LOOPUNTILflag1=0ANDflag2=0
FORi=1TOl
y$=MID$(x$,i,1):a(VAL(y$))=a(VAL(y$))+1
NEXTi
i=1
WHILEa(i)=0
i=i+1
WEND
PRINTLTRIM$(STR$(i));:a(i)=a(i)-1
FORj=0TO9
IFa(j)>0THENFORk=:NEXTk
NEXTj
PRINT
END

灵活的字符串
3、第十三界世界杯足球赛进入前八名的国家有：
ARGENTINE(阿根廷)ENGLAND(英格兰)SPAIN(西班牙)BELGIUM(比利时)GERMANY(德国)MEXICO(墨西哥)FRANCE(法国)BRAZIL(巴西)
这八个国家的英文名称藏在如下一个字块中：
AMUIGLEBP
PRWYUVWRQ
WVGSTEXAR
QNQECYMZY
HORNNZEIN
WPAGLTXLA需要设计一个程序查找这八个国名的第一个字
JRMLKJILM母所在的行、列号以及字母走向。字母走向规定为
FSPAINCNR八个方向，分别用八个字符串加以标注，如下图1，
AKWNGFOIE在打印查找结果时，需按国名字符串的先后顺序来
BPJDCDEHG输出查找结果。输出格式规定为：
NAME(国名)ROW(行)COL(列)DIRECTION(走向)
ARGENTINE11DOWNRIGHT
BELGIUM18LEFT
........
........
算法分析:
(1)建立数组a$(8)，b$(11),c$(8)，m1(8),m2(8)。
(2)对数组s$进行从小到大的排序。
(3)循环:k从1到8，反复执行:
循环:从字块的(i,j+1)对应位置上查找第k个国家的字符；
(i=1,2,…10；j=1,2,…9)
若mid$(b$(i),j+1,1)=mid$(a$(k),l,1))
则循环:从八个方向(l＝1,2,…,8)，搜索a$(k)
h记录搜索的字符串长度,i1和j1记录在某一搜索方向的下标
若h＝len(a$(k))则匹配成功，输出首字符位置(i,j)和字母走向c$(k).
否则，若mid$(b$(i1),j1,1)<>mid$(a$(k),h,1)则跳出循环，表示该方向匹配不成功。
CLS
DIMa$(10),b$(11),c$(8),m1(8),m2(8)
DATA"*amuiglebp*","*prwyuvwrq*","*wvgstexar*","*qnqecymzy*","*hornnzein*"
DATA"*wpagltxla*","*jrmlkjilm*","*fspaincnr*","*akwngfoie*","*bpjdcdehg*"
DATA"argentine","england","spain","belgium","germany","mexico","france","brazi"
DATA1,0,-1,-1,-1,0,