我认为用冒泡法对链表进行排序很蠢，元芳，这事儿你怎么看？

sonicling

回复 20# hbmhalley


    因为数组上的插入是基于二分搜索的。

hbmhalley

回复 24# sonicling


    so? 数组元素的移动也能做到 logn ?

hbmhalley

pmerofc 发表于 2012-11-19 20:45
回复 18# hbmhalley
描述一下冒泡的算法如何？
   我觉得不可能和11楼一样

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef struct _node_t {
   
5.         int w ;
   
6.         struct _node_t *n ;
   
7. } node_t ;
   
8. 
   
9. node_t *head = NULL ;
   
10. 
    
11. void ins (int k) {
    
12.         node_t *t = malloc (sizeof(node_t)) ;
    
13.         t->w = k ;
    
14.         t->n = head ;
    
15.         head = t ;
    
16. }
    
17. 
    
18. void print () {
    
19.         node_t *t ;
    
20.         for (t = head ; t != NULL ; t = t->n) {
    
21.                 printf ("%d\n" , t->w) ;
    
22.         }
    
23.         puts ("") ;
    
24. }
    
25. 
    
26. void sort () {
    
27.         int flag ;
    
28.         do {
    
29.                 flag = 0 ;
    
30.                 node_t **i ;
    
31.                 for (i = &head ; (*i)->n != NULL ; i = &(*i)->n) {
    
32.                         node_t *j = (*i)->n ;
    
33.                         if ((*i)->w > j->w) {
    
34.                                 flag = 1 ;
    
35.                                 (*i)->n = j->n ;
    
36.                                 j->n = *i ;
    
37.                                 *i = j ;
    
38.                         }
    
39.                 }
    
40.         } while (flag) ;
    
41. }
    
42. 
    
43. int main () {
    
44.         int t ;
    
45.         while (scanf ("%d" , &t) == 1) {
    
46.                 ins (t) ;
    
47.         }
    
48. 
    
49.         print () ;
    
50.         sort () ;
    
51.         print () ;
    
52. 
    
53.         return 0 ;
    
54. }
    

复制代码

1. (for ((i=0;i<9;++i));do echo $RANDOM; done)|./temp.exe

复制代码

hbmhalley

回复 27# pmerofc


    但 11L 不是原地排序.
    看错了.

    但不影响. 不过是交换与插入的区别罢了.
    不如你也把代码写出来.

    不对. 11L 确实不是原地排序

hbmhalley

回复 29# pmerofc


    囧 .. 改乱了.再贴一遍

不过是交换与插入的区别罢了.
不如你也把代码写出来.