使用链表实现冒泡排序有什么问题？

Question

原来如此，我需要在链表上实现冒泡排序算法。是的，我在 Stack Overflow 中看到了很多解决这个问题的答案。几乎所有这些都是使用指向指针的指针实现的。在这里，我尝试使用引用指针而不是双指针来实现这一点。我花了一天多的时间来弄清楚我的代码有什么问题。

我实现的冒泡排序和交换函数如下：

struct node
{
    int data;
    node* next;
    node(int x)
    {
        data = x;
        next = NULL;
    }
};

node* swap(node *a, node *b){
    node* temp = b->next;
    b->next = a;
    a->next = temp;
    return b;
}

void bubbleSort(node*& head) {
    node* ptr = head;
    node* last = NULL;
    int swapped;
    do
    {
        swapped = 0;
        ptr = head;

        while (ptr->next != last)
        {
            if (ptr->data > ptr->next->data)
            {
                if (ptr == head)
                {
                    head = swap(ptr, ptr->next);
                    swapped = 1;
                }

                else{
                    ptr = swap(ptr, ptr->next);
                    swapped = 1;
                }
                
            }

            ptr = ptr->next;
            
        }
        
    } while (swapped);
    
}

以上代码（错误）的输出如下：

The original list = 
2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 

The Sorted list = 
1 -> 2 -> 4 -> 6 ->

我知道这对你们大多数人来说都是一些基础知识。但是，如果您能花点时间看看这段代码有什么问题，我将不胜感激。

事实是我使用引用指针完成了与双指针相同的事情。例如，this bubble-sort implementation is done using double-pointers?

Answer 1

交换对于列表来说有点特殊。交换 2 个连续的节点涉及接触 4 个节点、2 个交换的节点以及它们之前的节点。这就是为什么 sort() 输出的列表长度与其输入长度不同的原因。

考虑到这一点，交换操作变成：

void swap_nodes(Node* a_pred, Node*& a, Node* b_pred, Node*& b)
{
    assert(a != nullptr && b != nullptr && b_pred != nullptr);
    assert(!a_pred || a_pred->next == a);
    assert(b_pred->next == b); 

    if (a == b)
        return;

    b_pred->next = a;
    if (a_pred)
        a_pred->next = b;

    Node* t = a->next;
    a->next = b->next;
    b->next = t;

    t = a;
    a = b;
    b = t;
}

此外，如果内循环中没有发生交换，则无法通过测试提前退出。这个测试只告诉你当前外层循环节点是最小的，直到结束，而不是范围完全排序。

跟踪被测试节点之前的节点很重要，因为不这样做意味着必须通过再次循环遍历列表来找到这些前导节点。

排序函数变为：

void sort(Node*& head)
{
    for (Node* a = head, *a_pred = nullptr; a != nullptr; a_pred = a, a = a->next)
    {
        for (Node* b = a->next, *b_pred = a; b != nullptr; b_pred = b, b = b->next)
        {
            if (b->data < a->data)
            {
               swap_nodes(a_pred, a, b_pred, b);
               if (a_pred == nullptr)
                   head = a;              
            } 
        }
    }
}

如果想优化一点，不能减少比较量，但是可以减少交换量，可以试试这个：

void sort(Node*& head)
{
    for (Node* a = head, *a_pred = nullptr; a != nullptr; a_pred = a, a = a->next)
    {
        // find smallest node value in [a, end)
        Node* small_pred = a_pred;
        Node* small = a;
        for (Node* b = a->next, *b_pred = a; b != nullptr; b_pred = b, b = b->next)
        {
            if (b->data < small->data)
            {
               small_pred = b_pred;
               small = b;
            }
        }

        if (small != a)
        {
           // remove smallest from list.
           small_pred->next = small->next;

           // insert smallest before a.
           small->next = a;
           if (a_pred == nullptr)       // same as a == head
               head = small;
           else 
               a_pred->next = small;

           // keep outer loop happy, by making it look like a swap.
           a = small;
        } 
        // node a is now the smallest node in range [a, end)
        // move on to the next.
    }
}

[编辑]

上面的冒泡排序是业界使用的。 “迂腐的”冒泡排序，出于某种未知的原因仍在教授这里：

void pedantic_bubble_sort(Node*& head) {
  for (Node* sentinel = nullptr; sentinel != head;) {
    bool swaps = false;

    for (Node *pred = nullptr, *a = head, *b = a->next; a && b;
         pred = a, a = b, b = b->next) {
      if (b->data < a->data) {
        swap_nodes(pred, a, a, b);
        if (!pred) head = a;
        swaps = true;
      }
      if (b->next == sentinel) {
        sentinel = b;
        break;
      }
    }

    if (!swaps) break;
  }
}

恕我直言，这个算法很慢。

你可以在这里修改它，并与其他算法和std::list::sort()比较性能：https://godbolt.org/z/Yco8WY

使用链表实现冒泡排序有什么问题？

What is wrong with this implementation of bubble sort using linked lists?

c++

sorting

pointers

pass-by-reference

bubble-sort