String list如何排序 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

String list如何排序

String list如何排序# JobHunting - 待字闺中

c*t2014-03-06 08:03

1 楼

好久不来了，问个排序问题。
Given a list of Strings
应该如何按字母顺序给String排序？
多谢！

s*x2014-03-06 08:03

2 楼

Princeton 大学那本书的经典算法，quicksort on first characters, then second,
then third. 3 way partition in each pass.

s*x2014-03-06 08:03

3 楼

http://algs4.cs.princeton.edu/51radix/

d*i2014-03-06 08:03

4 楼

,
请问前辈Princeton那本书名叫啥？

【在 s**x 的大作中提到】

: Princeton 大学那本书的经典算法，quicksort on first characters, then second,
: then third. 3 way partition in each pass.

s*x2014-03-06 08:03

5 楼

不敢当阿，就是那本 Robert Sedgewick 写的algorithms.
书真好，比clrs 好太多了，简单易懂，java code.
尽管我只写c++.
Trie, quicksort, 讲的很好。

【在 d********i 的大作中提到】

:
: ,
: 请问前辈Princeton那本书名叫啥？

s*x2014-03-06 08:03

6 楼

确实最值得看。
我当时偷懒，就下了电子版，很内疚。

【在 s**x 的大作中提到】

:
: 不敢当阿，就是那本 Robert Sedgewick 写的algorithms.
: 书真好，比clrs 好太多了，简单易懂，java code.
: 尽管我只写c++.
: Trie, quicksort, 讲的很好。

c*t2014-03-06 08:03

7 楼

多谢，如果是只包含小写字母的字符串，只用trie行不行？时间最佳。

【在 s**x 的大作中提到】

:
: 确实最值得看。
: 我当时偷懒，就下了电子版，很内疚。

s*x2014-03-06 08:03

8 楼

不是很清楚，忘了那个算法的复杂度了，感觉一般，复杂度可能差不多，还耗更多
space.

【在 c********t 的大作中提到】

: 多谢，如果是只包含小写字母的字符串，只用trie行不行？时间最佳。

c*t2014-03-06 08:03

9 楼

如果加入trie的时候，需要为每个node排序，那复杂度就差不多了。
我的想法，干脆用空间换时间，如果全是小写，干脆preconstruct一个每个节点都分支
26个字母的tri, 深度是最长字符串的长度。然后就简单了。O(n) 这个对很大的list
of Strings应该是很好的优化吧。
可行不？

【在 s**x 的大作中提到】

: 不是很清楚，忘了那个算法的复杂度了，感觉一般，复杂度可能差不多，还耗更多
: space.

c*t2014-03-06 08:03

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*x2014-03-06 08:03

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*t2014-03-06 08:03

12 楼

Thanks a lot!!!

【在 s**x 的大作中提到】

: http://algs4.cs.princeton.edu/lectures/51StringSorts.pdf
: 这里面讲了好几种。自己看看吧。