c - 对单向链表进行排序 - 我不明白

Question

我正在查看 http://publications.gbdirect.co.uk/c_book/chapter6/structures.html 中的示例 6.7|

(为方便起见粘贴在这里)

struct list_ele *
sortfun( struct list_ele *list )
{

      int exchange;
      struct list_ele *nextp, *thisp, dummy;

      /*
       * Algorithm is this:
       * Repeatedly scan list.
       * If two list items are out of order,
       * link them in the other way round.
       * Stop if a full pass is made and no
       * exchanges are required.
       * The whole business is confused by
       * working one element behind the
       * first one of interest.
       * This is because of the simple mechanics of
       * linking and unlinking elements.
       */

      dummy.pointer = list;
      do{
              exchange = 0;
              thisp = &dummy;
              while( (nextp = thisp->pointer)
                      && nextp->pointer){
                      if(nextp->data < nextp->pointer->data){
                              /* exchange */
                              exchange = 1;
                              thisp->pointer = nextp->pointer;
                              nextp->pointer =
                                      thisp->pointer->pointer;
                              thisp->pointer->pointer = nextp;
                      }
                      thisp = thisp->pointer;
              }
      }while(exchange);

      return(dummy.pointer);
}

我了解基本概念，但我无法真正解释其中发生的事情。有人可以更深入但简单地解释排序功能中发生了什么吗？

一般的一些问题:

• 为什么需要 dummy.pointer = list;？ dummy 然后在函数的末尾返回，为什么列表仍然排序？
• 评论整个业务都因在第一个感兴趣的元素后面工作一个元素而感到困惑。是什么意思？

Answer 1

dummy 是一个局部变量，首先设置为列表的开头。临时变量thisp 被设置为指向dummy，所以当它被更新时，dummy 指向的内容也会被更新。因此，dummy.pointer 最终将指向排序列表的新开始元素。 list 仍将指向列表的原始开头，因此返回值以便可以更新头指针。

我认为他们所说的混淆的意思是我们感兴趣的元素是nextp，而不是当前元素(或thisp)。也就是说，我们将列表中的下一个元素与当前元素进行比较，而不是将当前元素与前一个元素进行比较。我想这很令人困惑，但我真的不这么认为。

注意:这是Bubble Sort .更好的排序算法是 Merge Sort , 在 http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html 实现.