d*********g
发帖数: 59 | 1 感觉bubble比较好implement，但是效率不高，请问可以用quick sort吗？有简单的
implement吗？ |
c***2
发帖数: 838 | 2 merge sort:
1) split list in half
2) recursion
3) merge sorted list
O(nlgon)
Insertion sort:
Build a new list by inserting new element in order.
O(n^2) |
h***n
发帖数: 276 | 3 quick有，不难，merge sort也是
随便拷贝一段代码给你看看吧
void quick_sort_list(list *list)
{
if (list == NULL)
return;
list->head = quick_sort_list_recursive(list->head);
}
list_node* quick_sort_list_recursive(list_node *node)
{
list_node *pivot, *less, *larger, *p, *next;
if (node == NULL)
return NULL;
less = larger = NULL;
pivot = node;
p = pivot->next;
pivot->next = NULL;
while (p) {
next = p->next;
if (p->data < pivot->data) {
p->next = less;
less = p;
} else {
p->next = larger;
larger = p;
}
p = next;
}
less = quick_sort_list_recursive(less);
larger = quick_sort_list_recursive(larger);
pivot->next = larger;
if (less) {
p = less;
while (p->next)
p = p->next;
p->next = pivot;
} else {
less = pivot;
}
return less;
}
【在 d*********g 的大作中提到】
: 感觉bubble比较好implement，但是效率不高，请问可以用quick sort吗？有简单的
: implement吗？
|
j********x
发帖数: 2330 | 4 list本身存在理由就不是为了高效的排序
吗？有简单的
【在 d*********g 的大作中提到】
: 感觉bubble比较好implement，但是效率不高，请问可以用quick sort吗？有简单的
: implement吗？
|
w**********y
发帖数: 1691 | 5 @ch222:
用merge sort是不是有问题啊? linked list不支持random access,那样的话还是O(
nlogn)么?
@justicezyx
展开说说该怎么回答呢? 是说要用一些常见的tree么?
俺是编程小白,请不要笑话俺问题的幼稚... |
c***2
发帖数: 838 | |
w**********y
发帖数: 1691 | |
r****o
发帖数: 1950 | 8
Since you can build a new list, why not build a new array ?
【在 c***2 的大作中提到】
: merge sort:
: 1) split list in half
: 2) recursion
: 3) merge sorted list
: O(nlgon)
: Insertion sort:
: Build a new list by inserting new element in order.
: O(n^2)
|
