C++ 冒泡排序双向链表

我知道冒泡排序可能不是最快的方法，但它是可以接受的。我只是在将算法调整为数组中的双链接列表时遇到麻烦。

我的双链表有一个 int 类型和一个 string 类型来保存数字和单词。我的列表是用插入排序来排序的，我编写了该插入排序来按字母顺序排序，现在我需要按数字顺序重新排序我的双链表，从最大到最小。

我的麻烦点是如何运行这个循环，以便它得到正确彻底的排序，而不仅仅是一次。

到目前为止，这是我所取得的成果：

void DblLinkedList::ReorderListNumeric()
{
dummy = new Node();
temphead = head;
temp = head->next;

while(tempTwo->next != NULL)
{
    if(temp->wordCount < tempTwo->wordCount)
    {               
        dummy->word = tempTwo->word;
        dummy->wordCount = tempTwo->wordCount;

        tempTwo->word = temp->word;
        tempTwo->wordCount = temp->wordCount;

        temp->word = dummy->word;
        temp->wordCount = dummy->wordCount;
    }
    temp = tempTwo;
    tempTwo = tempTwo->next;
}
}

我的麻烦点是如何运行这个循环，以便它得到正确彻底的排序，而不仅仅是一次。

如果您已经有一个循环可以成功执行一次传递并且交换也可以，那么相对有效地执行多次传递的通常方法是：

set swapped = true
while swapped:
    set swapped = false
    do your one pass, setting swapped to true whenever you swap

This avoids the naive n² solution that beginners will invariably start with.

确实如此。

You set swapped to true这样您最初输入列表然后将其设置为false立即，在循环内。

您的单次通行证将设置swapped仅当发生交换时。如果您的传递中没有发生交换，则列表将被排序并退出循环。

If any交换发生时，swapped标志已设置，您将需要运行另一遍。这是因为交换可能位于列表的末尾，并使之前的订单无效，例如：

Initial: 1   2   3   4   6   7   5
  Pass1: 1   2   3   4   6   5<=>7 (swap)
  Pass2: 1   2   3   4   5<=>6   7 (swap)
  Pass3: 1   2   3   4   5   6   7 (no swap, so exit loop)

因此，假设您的代码是正确的，请从以下内容开始：

void DblLinkedList::ReorderListNumeric() {
    Node *ptr, *dummy = new Node();

    // Zero or one element, no sort required.

    if (head == NULL) return;
    if (head->next == NULL) return;

    // Force initial entry.

    int swapped = 1;
    while (swapped) {
        // Flag as last time, then do one pass.

        swapped = 0;

        ptr = head;
        while (ptr->next != NULL) {
            if (ptr->wordCount < ptr->next->wordCount) {
                // Swapping, need another pass.

                swapped = 1;

                dummy->word = ptr->word;
                ptr->word = ptr->next->word;
                ptr->next->word = dummy->word;

                dummy->wordCount = ptr->wordCount;
                ptr->wordCount = ptr->next->wordCount;
                ptr->next->wordCount = dummy->wordCount;
            }
            ptr = ptr->next;
        }
    }
}