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

sonicling

回复 25# hbmhalley


    我想错了。

pitonas

很愚蠢
是很愚蠢

liuiang

你们觉得类似于以下的序列：

1 3 5 2 4 6 7 9 11 8 10 12 .... .... 9997 9999 10001 9998 10000 10002

我应该插入啊还是插入啊还是插入啊~~~~~~~~

hbmhalley

回复 36# pmerofc


    没必要拆成这么多吧 .. 看着累

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_bubble () {
    
27.         node_t **i ;
    
28.         int flag ;
    
29. 
    
30.         do {
    
31.                 flag = 0 ;
    
32.                 for (i = &head ; (*i)->n != NULL ; i = &(*i)->n) {
    
33.                         node_t *j = (*i)->n ;
    
34.                         if ((*i)->w > j->w) {
    
35.                                 flag = 1 ;
    
36.                                 (*i)->n = j->n ;
    
37.                                 j->n = *i ;
    
38.                                 *i = j ;
    
39.                         }
    
40.                 }
    
41.         } while (flag) ;
    
42. }
    
43. 
    
44. void sort_insert () {
    
45.         node_t *nhead = NULL , *i , *next , **j ;
    
46.         for (i = head ; i != NULL ; i = next) {
    
47.                 next = i->n ;
    
48.                 for (j = &nhead ; *j != NULL && (*j)->w < i->w ; j = &(*j)->n)
    
49.                         ;
    
50. 
    
51.                 i->n = *j ;
    
52.                 *j = i ;
    
53.         }
    
54. 
    
55.         head = nhead ;
    
56. }
    
57. 
    
58. int main () {
    
59.         int t ;
    
60.         while (scanf ("%d" , &t) == 1) {
    
61.                 ins (t) ;
    
62.         }
    
63. 
    
64.         print () ;
    
65.         sort_insert () ;
    
66.         print () ;
    
67. 
    
68.         return 0 ;
    
69. }
    

复制代码

正好对比一下.
相对应用于数组的同类算法, 插入排序确实显示出链表的优势 ( i->n = *j ; *j = i ; ) 虽然对复杂度无影响
冒泡虽没有插入排序的简洁, 但代码结构与数组上的冒泡并无太大差别 (flag / for_all / 三行swap)

代码长度差距不大.

群雄逐鹿中原

pmerofc 发表于 2012-11-20 17:44
回复 30# hbmhalley

献丑。请多指教

元方，这不就是一下多冒几个泡排序算法吗？