17-一维数组查找、排序

《17-一维数组查找、排序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一维数组应用（查找、排序）例一：查找数组A中是否有等于NUM的这个数，有，则返回这个数在数组中的位置；没有，则返回0。（假设A中有N个互异的整数）程序：CONSTN=10；VARA：=ARRAY[1．．N]OFINTEGER；P，X：INTEGER；BEGIN给数组A赋初值；WRITELN（‘PLEASEINPUTX：’）；READLN（X）；P：=N；WHILE（A[P]<>X）AND（P>0）DOP：=P-1；IFA[P]〈〉XTHENP：=0；WRITELN（P）；END.改进：多定义1个A[0]，即VARA：=ARRAY[0．．N]OFINTEGER；然后：P：=N；A

2、[0]：=X；WHILEA[P]〈〉XDOP：=P–1；其中A[0]称为哨兵，减少了比较次数。例二：在一个已经排好序的数组中查找某一个数。有则返回这个数在数组中的位置，没有则返回0。（假设A中有N个互异的整数）分析：可以用例一方法，但效率低，下面用“二分法”程序：CONSTN=10；VARA：ARRAY[1．．N]OFINTEGER；I，J，K，P，X：INTEGER；FIND：BOOLEAN；BEGINWRITELN（‘INPUTAORDEREDARRAY：’）；FORI：=1TONDOREAD(A[I])；READLN；WRITE（‘INPUTX：’）；READLN（X）；

3、I：=1；J：=N；FIND：=FALSE；WHILE（NOTFIND）AND（IXTHENJ：=K–1ELSEI：=K+1；END；IFFINDTHENP：=KELSEP：=0；WRITELN（P）；END.例三：有N个数存放于数组A中，将其按照从小到大的顺序重新排列。选择排序法：用“打擂台”法将最小的1个数找出来放在数组的最前面。然后在剩下的N-1个数中重复做上面的操作………..，一共要N–1趟。CONSTN=10；VARA：ARRAY[1．．N]OFINTEG

4、ER；I，J，P，T：INTEGER；BEGINFORI：=1TONDOREAD（A[I]）；READLN；FORI：=1TON-1DO{重复N-1次}BEGINP：=I；{假设A[I]最小，后面的元素与它进行打擂台}FORJ：=I+1TONDOIFA[J]

5、]），若“逆序（前面的元素>后面的元素）”则交换。经过N–1趟，则排序结束。（或无交换，则结束。效率更高）。作用是：每次将大数放在后面，一趟过后最大者就在最后面了，再比较前面若干个数。CONSTN=10；VARA：ARRAY[1．．N]OFINTEGER；I，K，T：INTEGER；EXCHANGE：BOOLEAN；BEGINFORI：=1TONDOREAD（A[I]）；READLN；K：=N；{K为计数器，控制N-1次}REPEATEXCHANGE：=FALSE；FORI：=1TOK–1DOIFA[I]>A[I+1]THENBEGINT：=A[I+1]；A[I+1]：=A[I

6、]；A[I]：=T；EXCHANGE：=TRUEEND；K：=K–1UNTIL（K=1）OR（NOTEXCHANGE）；FORI：=1TONDOWRITE（A[I]：6）；WRITELNEND.后记：1、若要将其按照从大到小的顺序排列，如何办？2、其它排序方法：插入排序（在上一节课例一的基础上引申），快速排序……..例四：用“筛选法”找出100以内的所有素数，并按每行10个数打印出来。分析：旧方法：FOR循环；“筛选法”思想：数组A：2345678910111213141516……….99100指针P删除2的倍数P删除3的倍数P删除5的倍数直到P=100/2为止注：并不真正删除

7、，只是作个标记（如置-1），P初始值为1，以后从前至后找第一个不等于-1的数组元数，重复删除…………程序：CONSTN=100；VARA：ARRAY[2．．N]OFINTEGER；{1不是素数}P，I，J，NEWP，M：INTEGER；BEGINFORI：=2TONDOA[I]：=I；P：=1；REPEATP：=P+1；WHILE（A[P]=-1）AND（P<=NDIV2）DOP：=P+1；IFA[P]<>-1THENNEWP：=A[P]；FORI：=P+1TONDOIF（A[I]<>-1）