最好的方法來排序一長串字符串

Question

我想知道排序一長串字符串與時間和空間效率的最佳方法。我更喜歡時間效率而非空間效率。

字符串可以是數字，字母，字母數字等。我不喜歡排序行爲像字母數字排序v/s字母排序只是排序本身。

以下我可以想到的一些方法。

1. 使用代碼例如：.Net框架的Arrays.Sort（）函數。我認爲這樣做的方式是計算字符串的哈希碼，並使用二分搜索將字符串插入到適當的位置。

2. 使用數據庫（例如：MS-sql）。我沒有這樣做。我不知道這將是多麼有效。

3. 使用像trie這樣的前綴樹數據結構。排序需要使用DFS（深度優先搜索） - O（| V | + | E |）時間遍歷樹樹的所有trie節點。 （搜索需要O（l）時間，其中l是要比較的字符串的長度）。

其他任何方式或數據結構？

Answer 1

你說你有一個數據庫，可能是字符串存儲在數據庫中。那麼你應該讓數據庫爲你做這項工作。它可能能夠利用索引，因此不需要實際對列表進行排序，而只需按照排序順序從索引中讀取它。

如果沒有索引，數據庫可能仍然可以幫助您。如果您只爲某個小的常量數k獲取前k行，例如100.當您使用帶有LIMIT子句的ORDER BY時，它允許SQL Server使用稱爲TOP N SORT的特殊優化，該優化以線性時間而不是O（n log （n））時間。

如果您的字符串不在數據庫中，那麼您應該使用.NET提供的功能。我認爲你不可能編寫比默認排序快得多的自定義代碼。

Answer 2

我找到了this paper，它使用了trie數據結構來有效地對大量字符串進行排序。儘管我沒有詳細研究過它。

Answer 3

Radix sort也可能是不錯的選擇，如果琴絃不是很長，例如，名單

Answer 4

讓我們假設你有一個字符串的大名單，而且名單長度爲N

使用基於像歸併，堆排序或快速排序排序算法的比較會給你一個

其中n是列表的大小，d是列表中所有字符串的最大長度。

在這種情況下，我們可以嘗試使用基數排序。設b爲基數，令d爲最大字符串的長度，則我們可以證明使用基數排序的運行時間爲。

此外，如果字符串是說，小寫英文字母的運行時間是

來源：MIT Opencourse算法講座教授。 Eric Demaine。