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

Question

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

Answer 1

取前三為什麼要排序？新開闢三個變數的空間保存中間結果就行了。

這種方法的複雜度是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

這不是典型的Top k問題嗎，你可以百度一下Top K

Answer 5

topn的如果說穩妥的答案堆排是沒有錯的 問題是這個3取的。 。 。這麼小的數

Answer 6

就是堆排序a

Answer 7

topk求解

Answer 8

如果想要最快，我覺得點陣圖排序是我見過的最快的了。