溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹“java位圖排序算法怎么實現”，在日常操作中，相信很多人在java位圖排序算法怎么實現問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”java位圖排序算法怎么實現”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！
算法要求
輸入：一個最多包含n個正整數的文件，其中每個數字都小于n（n=10^7）沒有重復文件
輸出：按照升序輸出
約束條件：只有1M左右的內存空間，足夠的磁盤空間。最多運行為幾分鐘，如果為10秒就不需要優化。
在我上學剛畢業那會曾經碰到過三個面試官提問我這道題，當時我第一次的回答是簡單的冒泡排序，面試官直接提醒了我，內存有限，后來我靈機一動，我可以借助第三方數據庫，先把它存到數據庫，然后order by順序查詢出來。很明顯，這是一個不是辦法的辦法。當然，我當時也是答非所問。但是現在回過頭來想一想，還是有辦法解決的。
問題分析
如果說我們把這些數據引入到內存進行排序顯然是不現實的，因為一部分n的大小都可能超過1M，這時我們可以考慮使用位圖排序。
實現概要
假設我們有一組 {3,1,8,5,4,9} 這樣的一組小于10數據。我們可以用如下字符串進行表示這個集合
0 1 0 1 1 1 0 0 1 1 其中代表集合中的數據表示為1，其它的為零
如果我們使用偽代碼可以如下實現：
1 初始化一個大小為n的數組
for n = [1,n);
bit[i] = 0
2 順序讀取每個文件中每一個數字
for each i;
bit[i] = 1;
3 輸出
for n = [0,n);
if(bit[i]==1)
print i;
java代碼實現
int[] arrs = {12,234,13,1,143,321,1411};//磁盤中的文件
int[] sorts = new int[2000];
for(int arr : arrs) {
sorts[arr] = 1;
}
for(int i=0;i<2000; i++) {
if(sorts[i] == 1) {
System.out.print(i+",");
}
}
到此，關于“java位圖排序算法怎么實現”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
