请教一个算法问题。

chenyajun5

ok，非常感谢大家。

cfqtree

原帖由 libin1983 于 6/30/06 13:27 发表

好办法！（当内存足够大时 :wink:）

那就稍稍修改一下qsort调用的partition函数

当partition返回的位数(该位前面的数都大于该位上的数,后面的数都小于该位上的数)大于200时
就减去该位及该位以后所有的数

crspo

构造一个大顶堆然后不断删除最顶元素应该也很快（似乎比qsort之后取前几个还要快)

liubinbj

STL 中partial_sort，nth_element，stable_partition都可实现

nth_element提取元素后不排序
partial_sort提取元素后排序
stable_partition稳定排序

都是专家写的，咱们写肯定不如他们的好，不如不写。

windyheart

#include <algorithm>
using namespace std;

bool Larger(int iNumber1, int iNumber2)
{
      if (iNumber1 > iNumber2) {
          return true;
      }else {
          return false;
      }
}
vector<int> intVector; // 在这个整数向量中保存你要处理的整数

vector<int>::iterator first = intVector.begin();
vector<int>::iterator last = intVector.end();

sort(first, last, Larger);

chenyajun5

原帖由 liubinbj 于 2006-6-30 18:48 发表
STL 中partial_sort，nth_element，stable_partition都可实现

nth_element提取元素后不排序
partial_sort提取元素后排序
stable_partition稳定排序

都是专家写的，咱们写肯定不如他们的好，不如不写。

请问，这3个都是c++中的函数么？俺没有用过c＋＋，没用过这些函数。。你的意思是参考这些函数然后进行改写？

chenyajun5

原帖由 windyheart 于 2006-6-30 21:35 发表
#include <algorithm>
using namespace std;

bool Larger(int iNumber1, int iNumber2)
{
      if (iNumber1 > iNumber2) {
          return true;
      }else {
          return false;
...

sort是什么排序函数？快速排序么？俺没用过c＋＋，麻烦解释这段代码含义。。

liubinbj

原帖由 chenyajun5 于 2006-7-1 22:12 发表


请问，这3个都是c++中的函数么？俺没有用过c＋＋，没用过这些函数。。你的意思是参考这些函数然后进行改写？

你想改专家写的？没必要把，用就是了。

windyheart

原帖由 chenyajun5 于 2006-7-1 22:18 发表


sort是什么排序函数？快速排序么？俺没用过c＋＋，麻烦解释这段代码含义。。

不好意思啊！以前给你写的解答有些问题！在linux下面应该是编译不过去的！（主要那时对sort还不太理解） 下面是正确的解答(我这里用了partial_sort，因为你只想从N个整数中找到M个最大的数）

#include <algorithm>
#include <functional>
using namespace std;


vector<int> intVector;
vector<int>::iterator first;
vector<int>::iterator last;

// 把你要排序的整数存到上面的整数向量中去
intVector.push_back(...);
......

// 现在你已近将N个数都装到intVector中了, 这样我们可以对intVector排序
first = intVector.begin();
last = intVector.end();
partial_sort(first, first + M, last, great<int>());

// 现在intVector中的前M个数已经是N个中最大的了

希望以上所说的能对你有些帮助！
        ^_^ (如果你想了解sort的用法，可以到我的博客中看我的一篇文章）

ghostwwl

我觉得这个问题如果要最快的话 锦标赛算法应该是最快的
就是建树比较 然后大的数能尽一级 最大的数自然就是root 然后左右子树 分别就是次大和第三大的数 以此类推 要钱m的 从root取起 取m个元素 就够了

锦标赛 还是蛮经典算法