菜鸟捉虫(44)

刘利锋 
2001年 44期

#1　　排序&查找新思路
　　　　排序方法有很多，如插入排序、交换排序、选择排序……如果使用一维数组作为存储结构，均需要对记录本身进行物理重排。但有时我们只是从许多数据中找出某几个最大数或最小数或任意数在这组数据中的位置而已，没必要浪费时间改变原序（进行物理重排）。例如我们从分数中找到排名第x名的成绩（见下表）:（^44020501a^）
　　　　int data[n]，n；
　　　　{
　　　　int i，j，Position；
　　　　int index[n]，index1，index2，index3；
　　　　int data1，data3，data18；
　　　　for（i=0；i<n；i++）　
　　　　{Position=0；/*Position 标记位置变量*/
　　　　for（j=0；j<n；j++）　
　　　　{
　　　　/*在一组数据中，有几个相同的数据存在，则排在后面的数据算大*/
　　　　if（data[j]>=data[i]）　
　　　　{
　　　　if（j<=i）&（data[j]==data[i]））  Position=Position；
　　　　else Position ++；
　　　　index[i]=n-Position；
　　　　}
　　　　}
　　　　/*例如找出排在第1位，第3位，第18位的数据*/
　　　　for（i=0；i<n；i++）　
　　　　if（index[i]==n  index1=i；
　　　　if（index[i]==n-2 index3=i；
　　　　if（index[i]==n-17 index18=i；
　　　　}
　　　　data1=data[index1]；
　　　　data3=data[index3]；
　　　　data18=data[index18]；
　　　　上面这个程序效率较低，需要循环nn次，但优点是能排出所有的数据的次序。但如果只要前三个大小的数据，则可用下面的方法。
　　　　FirstCh=SecondCh=ThirdCh=0；/*第一，第二，第三全初始化为0*/
　　　　Void SearchPosition（data[]）　
　　　　int data[n]，n；
　　　　{
　　　　int i；
　　　　int FirstCh=ThirdCh=SecondCh=0
　　　　for（i=1；i<72；i++）　
　　　　{
　　　　if（data[i]>=data[FirstCh]）
　　　　{
　　　　ThirdCh=SecondCh；
　　　　SecondCh=FirstCh；
　　　　FirstCh=i；
　　　　}
　　　　else if（data[i]>=data[SecondCh]）
　　　　{
　　　　ThirdCh=SecondCh；
　　　　SecondCh=i；
　　　　}
　　　　else if（data[i]>=data[ThirdCh]）　
　　　　{
　　　　ThirdCh=i；
　　　　}
　　　　}
　　　　}
　　　　后面这个程序效率较高，只需循环n次，就可找出三个最大值，但只适用于找出几个排列靠前的数据。
　　
　　 
 