s****a
发帖数: 528 | |
q****x
发帖数: 7404 | 2 merge sort ok bah
【在 s****a 的大作中提到】
: 大家写过这样的程序吗？
|
b*****c
发帖数: 1103 | |
s****a
发帖数: 528 | 4 qsort 的话如何 randomize pivot 呢？ |
b*****c
发帖数: 1103 | 5 不random , 用mid of 3 or mid of 9 |
i**********e
发帖数: 1145 | 6 singly linked list 就可以做到 n log n 了。
用merge sort，in-place merge。
linked list 没有像数组那样可以 random access in O(1)，quick sort 不适用。 |
b*****c
发帖数: 1103 | |
a*****n
发帖数: 158 | 8 可以从２个开始MERGE啊，就象前几天那个LINK LIST REVERSE一样吧。。。 |
i**********e
发帖数: 1145 | |
s*****k
发帖数: 18 | 10 我觉得mergesort应该是O(n2)
T(n) = 2n + 2T(n/2) -> O(n^2)
【在 i**********e 的大作中提到】
: 这里有解：
: http://cslibrary.stanford.edu/105/LinkedListProblems.pdf
: 关键在于实现 merge() 函数，可以用递归写，简洁很多。
|
H*M
发帖数: 1268 | 11 ?
a typical nlgn
【在 s*****k 的大作中提到】
: 我觉得mergesort应该是O(n2)
: T(n) = 2n + 2T(n/2) -> O(n^2)
|
