c********t
发帖数: 5706 | 1 好久不来了，问个排序问题。
Given a list of Strings
应该如何按字母顺序给String排序？
多谢！ |
s**x
发帖数: 7506 | 2 Princeton 大学那本书的经典算法，quicksort on first characters, then second,
then third. 3 way partition in each pass. |
s**x
发帖数: 7506 | |
d********i
发帖数: 582 | 4
,
请问前辈Princeton那本书名叫啥？
【在 s**x 的大作中提到】
: Princeton 大学那本书的经典算法，quicksort on first characters, then second,
: then third. 3 way partition in each pass.
|
s**x
发帖数: 7506 | 5
不敢当阿，就是那本 Robert Sedgewick 写的algorithms.
书真好，比clrs 好太多了，简单易懂，java code.
尽管我只写c++.
Trie, quicksort, 讲的很好。
【在 d********i 的大作中提到】
:
: ,
: 请问前辈Princeton那本书名叫啥？
|
s**x
发帖数: 7506 | 6
确实最值得看。
我当时偷懒，就下了电子版，很内疚。
【在 s**x 的大作中提到】
:
: 不敢当阿，就是那本 Robert Sedgewick 写的algorithms.
: 书真好，比clrs 好太多了，简单易懂，java code.
: 尽管我只写c++.
: Trie, quicksort, 讲的很好。
|
c********t
发帖数: 5706 | 7 多谢，如果是只包含小写字母的字符串，只用trie行不行？ 时间最佳。
【在 s**x 的大作中提到】
:
: 确实最值得看。
: 我当时偷懒，就下了电子版，很内疚。
|
s**x
发帖数: 7506 | 8 不是很清楚， 忘了那个算法的复杂度了， 感觉一般， 复杂度可能差不多， 还耗更多
space.
【在 c********t 的大作中提到】
: 多谢，如果是只包含小写字母的字符串，只用trie行不行？ 时间最佳。
|
c********t
发帖数: 5706 | 9 如果加入trie的时候，需要为每个node排序，那复杂度就差不多了。
我的想法，干脆用空间换时间，如果全是小写，干脆preconstruct一个每个节点都分支
26个字母的tri, 深度是最长字符串的长度。然后就简单了。O(n) 这个对很大的list
of Strings应该是很好的优化吧。
可行不？
【在 s**x 的大作中提到】
: 不是很清楚， 忘了那个算法的复杂度了， 感觉一般， 复杂度可能差不多， 还耗更多
: space.
|
c********t
发帖数: 5706 | 10 想想这个space用的太大 26^26^26...，不太可行
其实也不需要preconstruction, 每个节点的children也不过是26个字母，如果各种字
符，也不过
256字符，用bucket sort, 也是O(1)
所以加入trie的时候, 并不需要太多时间。
【在 c********t 的大作中提到】
: 如果加入trie的时候，需要为每个node排序，那复杂度就差不多了。
: 我的想法，干脆用空间换时间，如果全是小写，干脆preconstruct一个每个节点都分支
: 26个字母的tri, 深度是最长字符串的长度。然后就简单了。O(n) 这个对很大的list
: of Strings应该是很好的优化吧。
: 可行不？
|
s**x
发帖数: 7506 | 11 http://algs4.cs.princeton.edu/lectures/51StringSorts.pdf
这里面讲了好几种。 自己看看吧。
【在 c********t 的大作中提到】
: 想想这个space用的太大 26^26^26...，不太可行
: 其实也不需要preconstruction, 每个节点的children也不过是26个字母，如果各种字
: 符，也不过
: 256字符，用bucket sort, 也是O(1)
: 所以加入trie的时候, 并不需要太多时间。
|
c********t
发帖数: 5706 | |
