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

一维数组应用（查找、排序） 例一：查找数组A中是否有等于NUM的这个数，有，则返回这个数在数组中的位置；没有，则返回0。（假设A中有N个互异的整数） 程序： CONST N = 10； VAR A：= ARRAY [ 1．．N ] 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 [ 0．．N ] 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 J ） DO BEGIN K：=（ I + J ） DIV 2 ； IF A[ K ] ：= X THEN FIND ：= TRUE ELSE IF A[ K ] 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 [ 1．．N ] OF INTEGER ； I，J，P，T：INTEGER ； BEGIN FOR I：= 1 TO N DO READ（A[ I ]）； READLN； FOR I：= 1 TO