17-一维数组的查找、排序.doc

一维数组应用（查找、排序）例一：查找数组A中是否有等于NUM的这个数，有，则返回这个数在数组中的位置；没有，则返回0。（假设A中有N个互异的整数）程序：CONST N = 10；VAR A：= ARRAY 1N OF INTEGER ； P，X ： INTEGER；BEGIN 给数组A赋初值； WRITELN（PLEASE INPUT X ： ）； READLN（X）； P ：= N； WHILE （ A P X）AND （ P 0 ） DO P：= P - 1； IF A P X THEN P：=0 ； WRITELN（P）；END.改进：多定义1个A 0 ，即VAR A：= ARRAY 0N OF INTEGER ； 然后： P：=N； A 0 ：= X ； WHILE A P X DO P ：= P 1 ； 其中A 0 称为哨兵，减少了比较次数。例二：在一个已经排好序的数组中查找某一个数 。有则返回这个数在数组中的位置，没有则返回0。（假设A中有N个互异的整数）分析：可以用例一方法，但效率低，下面用“二分法”程序：CONST N = 10； VAR A：ARRAY 1 N OF INTEGER ； I，J，K，P，X ：INTEGER ； FIND：BOOLEAN ； BEGIN WRITELN（INPUT A ORDERED ARRAY ：）； FOR I ：= 1 TO N DO READ (A I ) ； READLN； WRITE（INPUT X： ）； READLN（X）； I：=1 ；J：= N ；FIND ：= FALSE ； WHILE （NOT FIND ）AND （I X THEN J：= K 1 ELSE I：= K + 1 ； END； IF FIND THEN P：= K ELSE P：= 0 ； WRITELN（P）； END.例三：有N个数存放于数组A中，将其按照从小到大的顺序重新排列。选择排序法：用“打擂台”法将最小的1个数找出来放在数组的最前面。 然后在剩下的N-1个数中重复做上面的操作.， 一共要N 1 趟。CONST N = 10 ；VAR A：ARRAY 1N OF INTEGER ； I，J，P，T：INTEGER ；BEGIN FOR I：= 1 TO N DO READ（A I ）； READLN； FOR I：= 1 TO N-1 DO 重复 N-1次 BEGIN P：= I ； 假设A I 最小，后面的元素与它进行打擂台 FOR J：= I + 1 TO N DO IF A J 后面的元素）”则交换。经过N 1 趟，则排序结束。（或无交换，则结束。效率更高）。作用是：每次将大数放在后面，一趟过后最大者就在最后面了，再比较前面若干个数。CONST N = 10 ；VAR A：ARRAY 1N OF INTEGER ； I，K，T：INTEGER ； EXCHANGE：BOOLEAN ；BEGIN FOR I：= 1 TO N DO READ（A I ）； READLN； K：=N ； K为计数器，控制 N-1 次 REPEAT EXCHANGE：=FALSE ； FOR I：= 1 TO K 1 DO IF A I A I + 1 THEN BEGIN T：=A I+1 ；A I+1 ：= A I ； A I ：= T ；EXCHANGE：= TRUE END； K ：= K 1 UNTIL （K = 1）OR （NOT EXCHANGE ）； FOR I：= 1 TO N DO WRITE（A I ：6）； WRITELNEND.后记：1、若要将其按照从大到小的顺序排列，如何办？ 2、其它排序方法：插入排序（在上一节课例一的基础上引申），快速排序.例四：用“筛选法”找出100以内的所有素数，并按每行10个数打印出来。分析：旧方法：FOR 循环； “筛选法”思想：数组A：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 .99 100 指针P 删除2 的倍数 P 删除3 的倍数 P 删除5 的倍数 直到 P=100/2为止注：并不真正删除，只是作个标记（如置-1），P初始值为1，以后从前至后找第一个不等于-1的数组元数，重复删除程序：CONST N=100 ；VAR A：ARRAY 2N OF INTEGER ； 1 不是素数 P，I，J，NEWP，M：INTEGER；BEGIN FOR I：= 2 TO N DO A I ：= I ；P：= 1 ；REPEAT P：=P + 1 ； WHILE （A P = -1） AND （P = N DIV 2 ）DO P：= P + 1 ； IF A P -1 THEN NEWP：= A P ； FOR I：= P + 1 TO N DO IF （A I -1 ） AND （ A I MOD NEWP = 0 ） THEN A I ：= -1 ；UNTIL （ NEWP N DIV 2 ）；M：= 0 ；FOR I：= 2 TO N DO IF A I -1 THEN BEGI