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然后在函数末尾返回，为什么列表仍然被排序？
• 评论The whole business is confused by working one element behind the first one of interest.是什么意思？

Answer 1

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

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

注意：这是气泡排序。更好的排序算法是合并排序，实现 http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html。

Answer 2

该算法通过列表查看每个列表项及其后面的列表项。如果它们出现故障，它们就会被切换。然后重复该过程。最终不会有任何不合适的事情，也不会有任何变化;此时，所有工作都已完成（如剩余零exchanged所示）。换句话说，上次通过列表时，没有任何内容可以互换。

假人用于跟踪列表本身（以防前 2 个列表项被切换）。使用它（而不仅仅是指向列表的简单指针，因为它也可以用作假的第一项，以便可以比较列表中的原始第一项。它消除了结果列表的第一个项目与原始列表的第一个项目不同的特殊情况的需要。

在纸上计算出 1、2、3 和 4 项的列表。然后，您将看到它是如何工作的。完成它时，尝试按顺序放置列表以启动并运行算法。然后交换列表中的 2 个项目并再次执行。

关于整个业务混乱的评论，恕我直言，它所指的只是您必须跟踪单链列表中的 3 个节点才能交换其中两个节点的事实。如果你的列表中有项目 A C B（目标是列表是 A B C），当你交换 B 和 C 时，你也必须有权访问 A - 它的"下一个节点"指针必须从 C 更改为 B。