84669 人學習
152542 人學習
20005 人學習
5487 人學習
7821 人學習
359900 人學習
3350 人學習
180660 人學習
48569 人學習
18603 人學習
40936 人學習
1549 人學習
1183 人學習
32909 人學習
最近有一个java大神，是蚂蚁支付宝的哦，问了我这么一个问题。我的回答是先将数组分解成两百个小数组或者更多，在开两百个thread进行排序，取最大，然后对这两百个数进行排序，取前三。其实我的思路根本就没有涉及到算法层面，也只是暴力破解。其实这不是最好的做法，因为这样会严重的浪费资源，然后他的回答是堆排序。我的问题是堆排序是怎样实现的，最好用代码体现出来。
业精于勤，荒于嬉;行成于思，毁于随。
取前三為什麼要排序？新開闢三個變數的空間保存中間結果就行了。
這種方法的複雜度是O(nk)，n是数据总量，k是要获取的数据数量。排序无论是堆排还是快排都是O(nlogn)。当k小于log(2, 10 ** 8)時還是有優勢的，太大了就退化成插入排序了。
O(nk)
O(nlogn)
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個數字…
這不是典型的Top k問題嗎，你可以百度一下Top K
topn的如果說穩妥的答案堆排是沒有錯的 問題是這個3取的。 。 。這麼小的數
就是堆排序a
topk求解
如果想要最快，我覺得點陣圖排序是我見過的最快的了。
取前三為什麼要排序？新開闢三個變數的空間保存中間結果就行了。
這種方法的複雜度是
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個數字…
這不是典型的Top k問題嗎，你可以百度一下Top K
topn的如果說穩妥的答案堆排是沒有錯的 問題是這個3取的。 。 。這麼小的數
就是堆排序a
topk求解
如果想要最快，我覺得點陣圖排序是我見過的最快的了。