請教一個算法問題。

chenyajun5

ok，非常感謝大家。

cfqtree

原帖由 libin1983 于 6/30/06 13:27 發(fā)表

好辦法！（當(dāng)內(nèi)存足夠大時 :wink:）

那就稍稍修改一下qsort調(diào)用的partition函數(shù)

當(dāng)partition返回的位數(shù)(該位前面的數(shù)都大于該位上的數(shù),后面的數(shù)都小于該位上的數(shù))大于200時
就減去該位及該位以后所有的數(shù)

crspo

構(gòu)造一個大頂堆然后不斷刪除最頂元素應(yīng)該也很快（似乎比qsort之后取前幾個還要快)

liubinbj

STL 中partial_sort，nth_element，stable_partition都可實現(xiàn)

nth_element提取元素后不排序
partial_sort提取元素后排序
stable_partition穩(wěn)定排序

都是專家寫的，咱們寫肯定不如他們的好，不如不寫。

windyheart

#include <algorithm>
using namespace std;

bool Larger(int iNumber1, int iNumber2)
{
      if (iNumber1 > iNumber2) {
          return true;
      }else {
          return false;
      }
}
vector<int> intVector; // 在這個整數(shù)向量中保存你要處理的整數(shù)

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

sort(first, last, Larger);

chenyajun5

原帖由 liubinbj 于 2006-6-30 18:48 發(fā)表
STL 中partial_sort，nth_element，stable_partition都可實現(xiàn)

nth_element提取元素后不排序
partial_sort提取元素后排序
stable_partition穩(wěn)定排序

都是專家寫的，咱們寫肯定不如他們的好，不如不寫。

請問，這3個都是c++中的函數(shù)么？俺沒有用過c＋＋，沒用過這些函數(shù)。。你的意思是參考這些函數(shù)然后進行改寫？

chenyajun5

原帖由 windyheart 于 2006-6-30 21:35 發(fā)表
#include <algorithm>
using namespace std;

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

sort是什么排序函數(shù)？快速排序么？俺沒用過c＋＋，麻煩解釋這段代碼含義。。

liubinbj

原帖由 chenyajun5 于 2006-7-1 22:12 發(fā)表


請問，這3個都是c++中的函數(shù)么？俺沒有用過c＋＋，沒用過這些函數(shù)。。你的意思是參考這些函數(shù)然后進行改寫？

你想改專家寫的？沒必要把，用就是了。

windyheart

原帖由 chenyajun5 于 2006-7-1 22:18 發(fā)表


sort是什么排序函數(shù)？快速排序么？俺沒用過c＋＋，麻煩解釋這段代碼含義。。

不好意思��！以前給你寫的解答有些問題！在linux下面應(yīng)該是編譯不過去的�。ㄖ饕�那時對sort還不太理解） 下面是正確的解答(我這里用了partial_sort，因為你只想從N個整數(shù)中找到M個最大的數(shù)）

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


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

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

// 現(xiàn)在你已近將N個數(shù)都裝到intVector中了, 這樣我們可以對intVector排序
first = intVector.begin();
last = intVector.end();
partial_sort(first, first + M, last, great<int>());

// 現(xiàn)在intVector中的前M個數(shù)已經(jīng)是N個中最大的了

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

ghostwwl

我覺得這個問題如果要最快的話 錦標(biāo)賽算法應(yīng)該是最快的
就是建樹比較 然后大的數(shù)能盡一級 最大的數(shù)自然就是root 然后左右子樹 分別就是次大和第三大的數(shù) 以此類推 要錢m的 從root取起 取m個元素 就夠了

錦標(biāo)賽 還是蠻經(jīng)典算法