一道java面試題，20億數(shù)字的文本排序，如何取前100？因?yàn)檫@是一個(gè)Java問(wèn)題，所以這是典型的TOPK問(wèn)題。首先取前100個(gè)數(shù)字構(gòu)建一個(gè)最小堆，然后依次從堆的頂部插入剩余的數(shù)字，同時(shí)調(diào)整堆。堆中最

一道java面試題，20億數(shù)字的文本排序，如何取前100？

因?yàn)檫@是一個(gè)Java問(wèn)題，所以這是典型的TOPK問(wèn)題。首先取前100個(gè)數(shù)字構(gòu)建一個(gè)最小堆，然后依次從堆的頂部插入剩余的數(shù)字，同時(shí)調(diào)整堆。堆中最后100個(gè)元素就是結(jié)果。空間復(fù)雜度為k，時(shí)間復(fù)雜度為nlogk

七種排序算法：bubble、select、insert、fast、bucket、shell、heap

其中，bubble是最簡(jiǎn)單、效率最低的排序方法，老師要求我們掌握選擇排序方法。

快速排序是最好的排序算法：首先，選擇一個(gè)邊界值，將大于和小于邊界值的數(shù)據(jù)分成兩部分；對(duì)于分開(kāi)的部分，重復(fù)此過(guò)程直到結(jié)束。

大量數(shù)據(jù)用哪種算法排序最好？

1、4字節(jié)表示的整數(shù)數(shù)為2^32≈40億，2字節(jié)表示的無(wú)符號(hào)整數(shù)數(shù)為2^16≈60000。

2、2G=2^31b≈20億字節(jié)。

3、為了找出出現(xiàn)次數(shù)最多的數(shù)字，應(yīng)記錄每個(gè)數(shù)字的出現(xiàn)次數(shù)。最快的方法是記錄每個(gè)數(shù)字在內(nèi)存中出現(xiàn)的次數(shù)。記錄方法是記錄相應(yīng)的存儲(chǔ)器地址數(shù)和相應(yīng)地址的存儲(chǔ)器單元數(shù)。但是，2G內(nèi)存只能記錄20億字節(jié)的數(shù)字，如果每個(gè)數(shù)字的出現(xiàn)次數(shù)大于255則會(huì)發(fā)生溢出，沒(méi)有風(fēng)險(xiǎn)。因此，這種方案是不可取的。

4、這樣，磁盤(pán)上只能記錄每次出現(xiàn)的次數(shù)。這樣，就在磁盤(pán)上創(chuàng)建了一個(gè)16g文件。每4個(gè)字節(jié)對(duì)應(yīng)一個(gè)整數(shù)，可以對(duì)應(yīng)40億個(gè)整數(shù)。用于記錄相應(yīng)整數(shù)的個(gè)數(shù)。

1. 初始化文件。

2. 依次讀取數(shù)據(jù)并用無(wú)符號(hào)整數(shù)記錄在磁盤(pán)文件中。如果發(fā)生溢出，則該數(shù)字是次數(shù)最多的數(shù)字。

3. 從文件中讀取每個(gè)數(shù)字的次數(shù)，用變量a記錄最高次數(shù)，用變量B記錄最高次數(shù)的數(shù)據(jù)，用文件依次記錄最高次數(shù)的數(shù)據(jù)。當(dāng)最大次數(shù)增加時(shí)，a1和B被設(shè)置為1，并且該數(shù)字被寫(xiě)入文件中。當(dāng)出現(xiàn)相同次數(shù)的數(shù)字b1時(shí)，該數(shù)字被寫(xiě)入文件的相應(yīng)位置，直到全部被讀取為止。

所以您根本不需要2G內(nèi)存。