从m个数中找出最小的2个，有快速的算法吗？

Question

一个数组序列M，例如 M={12, 34, 54, 43, 23, 11, 10, 9, 9, 10, 9, 10}，
        
元素个数m<20。
                        
要求从一堆数中找出最小的2个数的标识号（按顺序从左要右编号, 从1开始计），
上例为：{7, 8, 9, 10, 11, 12}。有没有快捷的方法，如果用排序（冒泡）然后再扫描一遍，把=最小的2个数做个标识（排序完了还要把最小的两个数找出来）。这样效率很低。有没有好的算法？

Answer 1

多谢，已有思路。   for(int i=0;i<list.Length-1;i++)
   {
    min=i;
    for(int j=i+1;j<list.Length;j++)
    {
     if(list[j]<list[min])
      min=j;
    }
    int t=list[min];
    list[min]=list[i];
    list[i]=t;
   }第一次算出最小的数，第二次算出剩下序列最小的数。

Answer 2

效率不行
int list[1000]
int min1=(list[0]>list[1])?list[0]:list[1];
int min2=(list[1]>list[1])?list[1]:list[0];
for(int i=0;i<1000-1;i++)
   {
    if((list[i]<min1)&&(list[i]>min2)
//等于的情况我没考虑，你可以自己想想看在两数之间付给较小的
    {
     mi1=list[i];
     }
    else if(list[i]<min2)//比最小的还小，付给最小的
    {
     min2=list[i]; 
     }   }

Answer 3

冒泡排序, 快速排序和希尔排序用在这里效率都是很低的，二分法也不行。To sdcer777(独钓雪):
还是步长排序法合算   // 步长排序是什么？上面我贴的只是我从网上搜到的选择排序的例子，我具体不是这么做的，
akiy(宏)的方法我正在看，不过好像他没有考虑太多等于的情况，一开始就要扫一遍，直到扫到两个不同的值，并区分两者的大小（耗费的时间也不少，不过他的方法是有一定意义的，我正在比较）。还有一点，大家要注意，我不是仅仅只找出最小的2个数是什么，还要把这些最小的2个数的ID记录下来，就是说要知道其中某个人是否在最小的2个数范围内。
用一个数组arrFlags[]记录，如果属于最小的2个数的记录为1, 不属于最小的2个数的记为0．
这个操作最好在搜索最小的2个数的同时记录。(而我用选择排序的方法正是这样做的）具体的代码等我待会贴，偶在吃饭~~~~~~~~~

Answer 4

其实我原来写的代码是写成VB的（写小玩艺我还是习惯用VB），我改成VC的了（确切一点是C的），我没有运行调试过。akiy(宏)的方法找最小的2个数不错，但是终归是要写入标识的（需要一次循环），
如果加上第一次搜索确定序列中前两个不相等的数并且区分其大小（一大一小，需要一次循环），再加上搜索min1,min2需要一次循环，一共是3次循环。我用选择排序改写的，一共也是三次循环，但其中的判断可能多了一些。但是akiy(宏)的方法也需要做不少判断，至于哪个方法好一点，还不知道，好像我的也不错了，如有可改进的地方，告诉我。代码如下：/*******************************************************
 * Function: SelectMinSort
 * Description: 把序列中最小的2个数的位置号找出来，无需排序
 * Output: 输出标志序列为或者ID集合都行，这里是前者
 * Param1: list[] 排序的序列
 * Param2: arrFlags[] 标志位数组
 * Param3: nPerson 人数，即list[]需排序的长度
 * Author: Shines
 * Date: 2003-03-17
 *******************************************************/
void SelectMinSort(int list[], int arrFlags[], int nPerson)
{
    int i;
    int minNumber, minSecond;    // 标志初始化，可以改为memset()
    for(i=0; i<nPerson; i++) { arrFlags[i]=0; }    // 找出最小的数
    minNumber = list[0];
    for(i=1; i<nPerson; i++)
    {
        if(list[i] < minNumber)
            minNumber = list[i];
    }    // 找出第二小的数，同时并把最小的数的标志写入
    minSecond = -1;
    for(i=0; i<nPerson; i++)
    {
        if(list[i] == minNumber)
            arrFlags[i] = 1;      // 写入最小的数的标志
        else if(minSecond == -1)
            minSecond = list[i];  // 第一次记录minSecond
        else(list[i] < minSecond)
            minSecond = list[i];
        // 其实这里可以写成下面这样，我只是想让大家看得更清楚一些
        //else(minSecond == -1 || list[i] < minSecond)
        //  minSecond = list[i];
    }    // 如果不是序列中的所有的数都相等，
    // 也就是说存在minSecond(第二小的数)的话，
    // 写入所有第二小的数的标志位
    if((minSecond != -1) && (minNumber != minSecond))
    {
        for(i=0; i<nPerson; i++)
        {
            if(list[i] == minSecond)
                arrFlags[i] = 1;
        }
    }
}

Answer 5

想了一下，从效率上讲，akiy(宏)的方法比我现在用的好的，而且第一次搜索是可以提前结束的，甚至在第一次找不出第二小的数的时候，可以把所有的标志位设为1，并返回，因为全部的数都一样，可以提前结束。

Answer 6

很显然只要一次循环就搞定了。
''以被赋初直a(1 to 20)dim min1 as long ,min2 as long '''''始终保持min1  >   min2
min1=&H7fffFFFFF,min2=&h7fffffff    '''min2,min1 先是最大直for i =1 to 20
if min1 > a(i) then 
     min1=a(i)
   if min1 <min2 then 
       swap (min1,min2)  ‘’交换
   endif
endif
next i

Answer 7

int i;
    int minNumber=0x7FFFFFFF, minSecond=0x7FFFFFFF;    for(i=0; i<nPerson; i++) { arrFlags[i]=0; }    for(i=0; i<nPerson; i++)
    {
        if(list[i] < minSecond)
        {
            minSecond = list[i];
            if(minSecond < minNumber)
                swap(minNumber, minSecond);
        }
    }    if(minSecond == 0x7FFFFFFF)
    {
        for(i=0; i<nPerson; i++)
        {
            if(list[i] == minNumber)
                arrFlags[i] = 2;    // 2为最小值
        }
    }
    else
    {
        for(i=0; i<nPerson; i++)
        {
            if(list[i] == minNumber)
                arrFlags[i] = 2;    // 2为最小值
            else if (list[i] == minSecond)
                arrFlags[i] = 1;    // 1为第二小的值
        }
    }