最近有一个java大神,是蚂蚁支付宝的哦,问了我这么一个问题。我的回答是先将数组分解成两百个小数组或者更多,在开两百个thread进行排序,取最大,然后对这两百个数进行排序,取前三。其实我的思路根本就没有涉及到算法层面,也只是暴力破解。其实这不是最好的做法,因为这样会严重的浪费资源,然后他的回答是堆排序。我的问题是堆排序是怎样实现的,最好用代码体现出来。
PHPz2017-04-18 09:15:57
取前三為什麼要排序?新開闢三個變數的空間保存中間結果就行了。
這種方法的複雜度是O(nk)
,n是数据总量,k是要获取的数据数量。排序无论是堆排还是快排都是O(nlogn)
。当k小于log(2, 10 ** 8)
時還是有優勢的,太大了就退化成插入排序了。
阿神2017-04-18 09:15:57
有N(N>>10000)個整數,求其中的前K個最大的數。 (稱作Top k演算法問題)。由於(1)輸入的大量資料;(2)只要前K個,對整個輸入資料的保存和排序是相當的不可取的。可以利用資料結構的最小堆來處理此問題。
最小堆,對於每個非葉子節點的數值,一定不大於孩子節點的數值。這樣可用含有K個節點的最小堆來保存K個目前的最大值(當然根節點是其中的最小數值)。每次有資料輸入的時候可以先與根節點比較。若不大於根節點,則捨棄;否則用新數值取代根節點數值。並進行最小堆的調整。
由於僅僅保存了K個數據,有調整最小堆的時間複雜度為O(logK),因此TOp K演算法(問題)時間複雜度為O(nlogK).
PHP中文网2017-04-18 09:15:57
隨手一搜尋
http://www.cnblogs.com/skywang12345/p/3610187.html
證明及推導參見演算法導論
但是可以不用堆吧,畢竟只找3個數字…