如何在java中執行內存有效的數組排序？

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

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

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

2011-05-13 Stephen

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

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

2011-05-13 02:41:36 dlev

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

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

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

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

2011-05-13 02:47:28

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

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

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

2011-05-13 03:26:51

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

回答