C++对双向链表进行冒泡排序

Question

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

我的双链表有一个 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;
}
}

Answer 1

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

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

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

这避免了初学者总是从简单的 n² 解决方案开始。

确实如此。

您将 swapped 设置为 true，以便您最初输入列表，然后在循环内立即将其设置为 false。

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

如果发生任何交换，则会设置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;
        }
    }
}

Answer 2

使用 2 个循环对列表进行彻底排序（我不考虑这里的效率，因为目前这对你来说并不重要）。因此，使用 2 个指针迭代列表，就像处理数组一样 -

void DblLinkedList::ReorderListNumeric()
{
    NODE* temphead = NULL; // assuming your list is made of NODEs
    NODE* temp = NULL;

    for(temphead = head; temphead && temphead->next != NULL; ++ temphead)
    {
        for(temp = temphead->next; temp && temp->next != NULL; ++temp)
        {
            if(temphead->wordCount < temp->wordCount)
            {
                std::string dummyWord = temp->word;
                int dummyCount = temp->wordCount;

                temp->word = temphead->word;
                temp->wordCount = temphead->wordCount;

                temphead->word = dummyWord;
                temphead->wordCount = dummyCount;
            }
        }
    }
}

顺便说一句，为什么要创建一个虚拟节点来交换，而您想要的只是交换值。