java - 有一个算法问题想请教，给定一亿个数，如何用最快的方法取出其中最大的三个数。

Question

最近有一个java大神，是蚂蚁支付宝的哦，问了我这么一个问题。我的回答是先将数组分解成两百个小数组或者更多，在开两百个thread进行排序，取最大，然后对这两百个数进行排序，取前三。其实我的思路根本就没有涉及到算法层面，也只是暴力破解。其实这不是最好的做法，因为这样会严重的浪费资源，然后他的回答是堆排序。我的问题是堆排序是怎样实现的，最好用代码体现出来。

Answer 1

上位 3 つを並べ替える必要があるのはなぜですか? 3 つの新しい変数スペースを開いて中間結果を保存するだけです。

この方法の計算量は O(nk)、n はデータの総量、k は取得するデータの数です。ヒープソートでもクイックソートでも順序はO(nlogn)です。 k が log(2, 10 ** 8) より小さい場合でも利点はありますが、大きすぎると挿入ソートに堕します。

Answer 2

N (N>>10000) 個の整数があり、その中で上位 K 個の最大の数値を見つけます。 (Top k アルゴリズム問題と呼ばれます)。 (1) 入力データが大量である、(2) 最初の K のみであるため、入力データ全体を保存して並べ替えることは非常に望ましくありません。この問題は、データ構造の最小ヒープを使用して処理できます。

最小ヒープ。各非リーフ ノードの値は、子ノードの値を超えてはなりません。このようにして、K 個のノードを含む最小ヒープを使用して、K 個の現在の最大値を保存できます (もちろん、ルート ノードはその中の最小値です)。データが入力されるたびに、最初にルート ノードと比較できます。ルート ノードより大きくない場合は破棄し、ルート ノードの値を新しい値に置き換えます。そして最小ヒープを調整します。

K 個のデータのみが保存されるため、最小ヒープの計算量は O(logK) に調整され、TOp K アルゴリズム (問題) の計算量は O(nlogK) となります。

Answer 3

検索してください
http://www.cnblogs.com/skywang12345/p/3610187.html

証明と導出については、「アルゴリズムの概要」を参照してください

でも、積み上げる必要はありません。結局のところ、探しているのは 3 つの数字だけです...

Answer 4

これは典型的なトップ K の質問ではありませんか? Baidu でトップ K を検索できます

Answer 5

topn の答えは、この 3 つを積み上げれば正解です。 。 。とても少ない数です

Answer 6

ヒープソートです

Answer 7

トップクソリューション

Answer 8

最速にしたいのであれば、ビットマップのソートが私がこれまで見た中で最も速いと思います。