如何使用冒泡排序对链表进行排序？ [英] How to sort a linked list using bubble-sort?

问题描述

我想使用bubble-sort为了排序链表。我使用curr和trail为了穿过列表。 curr应该总是领先一步。这是我的代码到目前为止：

I am trying to use bubble-sort in order to sort a linked list. I use curr and trail in order to traverse thru the list. curr is supposed to be one step ahead of trail always. This is my code so far:

void linked_list::sort ()
{
  int i,j=0;
  int counter=0;
  node *curr=head;
  node *trail=head;
  node *temp=NULL;

  while (curr !=NULL)
  {
    curr=curr->next;    //couting the number of items I have in my list. 
    counter++;          //this works fine.
  }

  curr=head->next;          // reseting the curr value for the 2nd position.

  for (i=0; i<counter; i++)
  {
    while (curr != NULL)
    {
      if (trail->data > curr->data)
      {
        temp=curr->next;      //bubble sort for the pointers.
        curr->next=trail;
        trail->next=temp;

        temp=curr;         //reseting trail and curr. curr gets back to be infront.
        curr=trail;     
        trail=temp;

        if (j==0)   //i'm using j to determine the start of the loop so i won't loose the head pointer.
        {
          head=trail;
        }

      }
      j++;
      trail=curr;
      curr=curr->next;   //traversing thru the list. nested loop.
    }

    trail=head;
    curr=trail->next;
    curr->next=trail->next->next;  //traversing thru the list. outer loop.
    j=0;
  }
}

我在这里缺少什么？

推荐答案

你缺少几件事情;最重要的是链表不是数组，因此你不能轻易地做某些算法，可以互换。请考虑以下因素：

You're missing several things; the most important being linked lists are not arrays, and as such you cannot easily do certain algorithms with both interchangeably. With that please consider the following:

• 列表长度由到达最后一个节点确定，但不需要它此算法。应该没有理由扫描列表只是为了找到你不需要的计数。当气泡排序的最后一个分段到达单个节点时（即它没有下一个到goto），达到完成状态。


• 链接列表（或任何其他节点指针模式）的秘密是操作指针。为此，你可以大大地利用你已经用于操纵你的节点的东西：指针，但不只是任何指针。

• List length is determined by reaching the last node, but you don't need it for this algorithm. There should be no reason to scan the list just to find a count that you don't need in the first place. Your "finished" state is reached when the last segment of the bubble sort reaches a single node (i.e. it has no next to goto).
• The secret to linked list (or any other node-pointer pattern) is the manipulation of the pointers. To that end, you can greatly utilize something you already use for manipulating your nodes: pointers, but not just any pointers. pointers to pointers.
• Never underestimate the power of a sheet of paper and a pencil to draw out how you want your algorithm to work. Especially for something like this:

现在看看下面一个截然不同的方法。有一些内容在理解整体算法是至关重要的，但我会保存它之后的代码：

Now take a look at the following considerably different approach. There is something within that is paramount to understanding the overall algorithm, but I'll save it for after the code :

void ll_bubblesort(struct node **pp)
{
    // p always points to the head of the list
    struct node *p = *pp;
    *pp = nullptr;

    while (p)
    {
        struct node **lhs = &p;
        struct node **rhs = &p->next;
        bool swapped = false;

        // keep going until qq holds the address of a null pointer
        while (*rhs)
        {
            // if the left side is greater than the right side
            if ((*rhs)->data < (*lhs)->data)
            {
                // swap linked node ptrs, then swap *back* their next ptrs
                std::swap(*lhs, *rhs);
                std::swap((*lhs)->next, (*rhs)->next);
                lhs = &(*lhs)->next;
                swapped = true;
            }
            else
            {   // no swap. advance both pointer-pointers
                lhs = rhs;
                rhs = &(*rhs)->next;
            }
        }

        // link last node to the sorted segment
        *rhs = *pp;

        // if we swapped, detach the final node, terminate the list, and continue.
        if (swapped)
        {
            // take the last node off the list and push it into the result.
            *pp = *lhs;
            *lhs = nullptr;
        }

        // otherwise we're done. since no swaps happened the list is sorted.
        // set the output parameter and terminate the loop.
        else
        { 
            *pp = p;
            break;
        }
    }
}

可能是预期的。这个简单的练习的目的是确定我们评估数据，但实际上是排序指针。注意除了 p ，它总是列表的头部，我们没有使用额外的指向节点的指针。

This is radically different than you probably expected. The purpose of this simple exercise is to establish that we're evaluating data, but we're actually sorting pointers. Notice that except for p, which is always the head of the list, we use no additional pointers to nodes. Instead we use pointers-to-pointers to manipulate the pointers buried in the list.

为了演示这个算法是如何工作的，我写了一个指向指针的指针来处理列表中小测试应用程序，使一个随机的整数列表，然后把上面的松散上述列表。我也写了一个简单的打印实用程序打印从任何节点到结束的列表。

To demonstrate how this algorithm works I've written a small test app that makes a random list of integers, then turns the above loose on said list. I've also written a simple print-utility to print the list from any node to the end.

void ll_print(struct node *lst)
{
    while (lst)
    {
        std::cout << lst->data << ' ';
        lst = lst->next;
    }
    std::cout << std::endl;
}

int main()
{
    std::random_device rd;
    std::default_random_engine rng(rd());
    std::uniform_int_distribution<int> dist(1,99);

    // fill basic linked list
    struct node *head = nullptr, **pp = &head;
    for (int i=0;i<20; ++i)
    {
        *pp = new node(dist(rng));
        pp = &(*pp)->next;
    }
    *pp = NULL;

    // print prior to sort.
    ll_print(head);
    ll_bubblesort(&head);
    ll_print(head);
    return 0;
}

我也修改了原始算法，

I've also modified the original algorithm to include printing after each pass that swaps something:

    *pp = *lhs;
    *lhs = nullptr;
    ll_print(p);

示例输出

6 39 13 80 26 5 9 86 8 82 97 43 24 5 41 70 60 72 26 95 
6 13 39 26 5 9 80 8 82 86 43 24 5 41 70 60 72 26 95 
6 13 26 5 9 39 8 80 82 43 24 5 41 70 60 72 26 86 
6 13 5 9 26 8 39 80 43 24 5 41 70 60 72 26 82 
6 5 9 13 8 26 39 43 24 5 41 70 60 72 26 80 
5 6 9 8 13 26 39 24 5 41 43 60 70 26 72 
5 6 8 9 13 26 24 5 39 41 43 60 26 70 
5 6 8 9 13 24 5 26 39 41 43 26 60 
5 6 8 9 13 5 24 26 39 41 26 43 
5 6 8 9 5 13 24 26 39 26 41 
5 6 8 5 9 13 24 26 26 39 
5 6 5 8 9 13 24 26 26 
5 5 6 8 9 13 24 26 
5 5 6 8 9 13 24 26 26 39 41 43 60 70 72 80 82 86 95 97

62 28 7 24 89 20 94 26 27 21 28 76 60 51 99 20 94 48 81 36 
28 7 24 62 20 89 26 27 21 28 76 60 51 94 20 94 48 81 36 
7 24 28 20 62 26 27 21 28 76 60 51 89 20 94 48 81 36 
7 24 20 28 26 27 21 28 62 60 51 76 20 89 48 81 36 
7 20 24 26 27 21 28 28 60 51 62 20 76 48 81 36 
7 20 24 26 21 27 28 28 51 60 20 62 48 76 36 
7 20 24 21 26 27 28 28 51 20 60 48 62 36 
7 20 21 24 26 27 28 28 20 51 48 60 36 
7 20 21 24 26 27 28 20 28 48 51 36 
7 20 21 24 26 27 20 28 28 48 36 
7 20 21 24 26 20 27 28 28 36 
7 20 21 24 20 26 27 28 28 
7 20 21 20 24 26 27 28 
7 20 20 21 24 26 27 
7 20 20 21 24 26 27 28 28 36 48 51 60 62 76 81 89 94 94 99 

请注意，只要我们在已经排序的段中留下了我们不断减少的源列表，我们就完成了。

Notice how as soon as we have an already-sorted segment left in our ever-decreasing source list, we're done.

摘要

上面的算法用一个调试器来理解它是如何工作的。事实上，我建议大多数算法，但是执行指针到指针操作的算法可能有点令人望而生畏，直到你知道真正的强大。这不是执行此任务的唯一方法，但如果您考虑如何管理链表，并且您真正做的是如何更改存储在可预测位置的指针中的值，那么这是一种直观的方法。

I strongly advise walking through the above algorithm with a debugger to understand better how it works. In fact, I advise that with most algorithms anyway, but algorithms that perform pointer-to-pointer actions can be a little daunting until you understand how powerful that really are. This is not the only way to do this task, but is an intuitive approach if you think about how linked lists are managed, and how all you're really doing is changing values stored in pointers in predictable places.

这篇关于如何使用冒泡排序对链表进行排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！