2011-05-13 29 views
7

我想排序大量的字符串(特別是File.list(),我不能外化或進一步減少),而不使用[多]額外的內存。如何在java中執行內存有效的數組排序?

Arrays.sort()表示它進行合併排序,而維基百科說,某些實現分配原始數組的大小來存儲排序的輸出。 (這似乎是由方法中的System.arraycopy引用所支持的)。

是否有一個內置的排序算法,我可以使用,而不是內存效率?

+1

您是否樂意手動編寫排序算法有多複雜,並且您希望它是否穩定(意味着等值元素以最初排列的順序出現在最終數組中)?並不是說你可以用String來區別這個區別,除非你開始查看'System.identityHashcode'或其他東西。 –

回答

6

快速排序就地且速度非常快。請參閱here

+0

好的 - 那太棒了; apache或谷歌有一個快速排序的庫嗎? (我確信我以前見過一個...) – Stephen

+0

quicksort速度非常快,但它也是更昂貴的排序之一,內存明智 –

+1

@Sam Quicksort可以就地實現,我相信它良好的記憶方式。 –

1

您可以編寫用於就地排序的堆排序算法。

5

String在Java中是不可變的。因此,當您的問題中String的數組重複時,它們不需要您期望的太多空間。實際上,開銷可能非常小。

換句話說,Java的Arrays#sort()對您的解決方案來說可以很好。你可以自己測試性能。

對於您的問題標題,Ankit的回答和dlev的回答都很好。

+1

要清楚的是,將被複制的只是對象*引用數組(通常每個字符串4或8個字節)而不是String對象本身,因此不是每個String內部的字符數組。 –