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

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

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

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

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

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

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

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

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

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

ヒープソートです

トップクソリューション

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