请教一个算法(问题仍未解决，继续请教中...)

daybreakcx

因为已经是排好序的了，所以iFindNum就是在第n位置上，即strData[iFindNum]位置，数据是strData[iFindNum].lData，原位置就是strData[iFindNum].iPos

titansword2000

问题是我在一楼贴的代码从打印出来的数据检验来看，现在有两个问题，第一：排序不成功；第二：序列也不对。  一直找不到问题出在哪。

daybreakcx

你的排序过程：
for(i=0;i<iArrayNum;i++)
        {lmin=strData.lData;
         iFlag=strData.iPos;

         for(j=i+1;j<iArrayNum;j++)
                {if(strData[j].lData<lmin)
                        {lmin=strData[j].lData;
                         iFlag=strData[j].iPos;
                        }
                }

         strData[iFlag].lData=strData.lData;
         strData[iFlag].iPos=strData.iPos;
         strData.lData=lmin;
         strData.iPos=iFlag;
        }

这个排序的过程是错误的，lmin的处理可以这样，但是你的iPos就不行了，那是原来的偏移，要改也是当前的坐标j，还有最后的将最小值放到合适的位置上也不对，因为你这样会进行一大堆覆盖操作，直接把东西给覆盖掉了，排序肯定不对，实际上如果你那样写是个选择排序那么是个交换的过程。我按照你的思路给一个可行的改变方案

sData temp;
for(i=0;i<iArrayNum;i++)
{
    k=i;
    for(j=i+1;j<iArrayNum;j++)
        if(strData[j].lData<strData[k].lData) k=j;
    if (k!=i)
    {
        temp=strData[k];
        strData[k]=strData;
        strData=temp;
    }
}

houhulou

M个数中N最小的数
创建个STRUCT用来保存VALUE AND POSiTION , 然后声明个VECTOR<STRUCT>  instance,
遍历M个数,把最小的N个数放到VECTOR里(按大小顺序排放),
其实把 VALUE 和 POSITION 放到MAP里比VECTOR要好些,MAP定位快

daybreakcx

其实差不多，因为map使用红黑树实现的，插入操作的复杂度是O(logm)的，你做m次插入然后再取出前n小的数值其实这个过程时间和直接做一次排序然后取前n个是一样的

houhulou

做不到M次插入 , 你先做一次比较 如果比最大的还要大, 就不需要插入,MAP里只保存<=N个数

daybreakcx

那我给个两个特殊例子，如果m=n呢，如果是逆序给的呢，这些都要实实在在插入m次的

houhulou

如果数据特别混乱的话 ,插入删除跟全部插入排序 ,不知道哪个快 ,制不了

daybreakcx

你完全可以试试看，把m开大一点，时间差别很是明显的

DraculaW

感觉有点像count sort