c++ - 链表的冒泡排序

Question

我正在尝试使用冒泡排序对单向链表进行排序。如果有一个简单的错误，请原谅。请告诉我哪里出错了。当我尝试这样做时，程序意外停止。

void sortBubble()
{
      Node *i=start,*j=start;Node *temp;Node* prev=start;Node* agla;
      while(i->next!=NULL)
      {
           cout<<"\nhello 1";
           j=i;
           agla=j->next;
           while(agla!=NULL)
           {
                temp=NULL;temp->next=NULL;
                cout<<"\nhello2";

                if(*(j) > *(agla))
                {
                     temp=agla->next;
                     agla->next=j;
                     prev->next=agla;
                     prev=agla;
                     agla=j->next;
                     j->next=temp;
                }
                else{
                     prev=j;
                     j=agla;
                     agla=j->next;}
                }
                prev=i;
                i=i->next;
           }
      }
 }

Answer 1

绝对会导致程序崩溃的第一个明显错误是:

       while(agla!=NULL)
       {
            temp=NULL;temp->next=NULL;

您正在将变量设置为 NULL，然后设置其字段。空指针指向任何地方，因此您无法编辑其内容。

删除 temp->next=NULL;

---

编辑:

您的程序逻辑不正确。在循环的几次迭代后，您破坏了列表，并且程序陷入了一个无限循环，其中包含混合的指针。

在冒泡排序中，我们多次遍历项目。在每次迭代中，最大的项目冒泡到列表的末尾。第一次迭代后，我们确定最大的元素在列表的末尾。第二次迭代后，我们确定第二大元素在列表的最后一个元素之前，依此类推。
重复此过程，直到所有项目都就位:

int getListSize(Node* start)
{
    int count = 0;
    while(start != NULL)
    {
        count++;
        start = start->next;
    }
    return count;
}

void bubbleSort(Node *&start) // <-- Pass a reference to pointer, because we may need to modify the start pointer.
{
    int size = getListSize(start);
    int i = 0;

    while(size--)
    {
        Node
            *current = start,
            *prev = NULL; // We are at the beginnig, so there is no previous node.

        while(current->next != NULL) // We have at least one node (size > 0) so `current` itself is not NULL.
        {
            Node *after = current->next;
            if((*current) > (*after))
            {
                //swap the items
                current->next = after->next;
                after->next = current;
                if (prev == NULL) // we are at the beginning
                    start = after;
                else
                    prev->next = after;

                prev = after;
            }
            else
            {
                prev = current;
                current = current->next;
            }
        }
    }
}

我们重复“冒泡”过程 size 次。这不是最有效的方法，因为我们甚至比较已经排序的项目。一种更有效的方法是排序，直到没有新的交换发生:

void bubbleSort(Node *&start) // <-- Pass a reference to pointer, because we may need to modify the start pointer.
{
    int size = getListSize(start);
    int i = 0;

    Node *lastSwapped = NULL;

    while(size--)
    {
        Node
            *current = start,
            *prev = NULL, // We are at the beginnig, so there is no previous node.
            *currentSwapped = NULL;

        while(current->next != lastSwapped) // We have at least one node (size > 0) so `current` itself is not NULL.
        {
            Node *after = current->next;
            if((*current) > (*after))
            {
                //swap the items
                current->next = after->next;
                after->next = current;
                if (prev == NULL) // we are at the beginning
                    start = after;
                else
                    prev->next = after;

                prev = after;
                currentSwapped = current;
            }
            else
            {
                prev = current;
                current = current->next;
            }
        }

        if (currentSwapped == NULL)
            break; // No swapping occured. The items are sorted.
        else
            lastSwapped = currentSwapped;
    }
}

This is the complete working program