C++冒泡排序双链表

Question

我知道冒泡排序可能不是最快的方法,但它可以接受.我只是在调整算法以将数组中的链接列表加倍时遇到问题.

我的双链表有一个int类型和一个类型字符串来保存数字和一个单词.我的列表是按照我按字母顺序排序的插入排序排序的,现在我需要以数字方式重新排序我的双链表,最大到最小.

我的麻烦在于如何运行这个循环,以便彻底正确排序,而不仅仅是一次.

这是我到目前为止所做的事情:

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;
        }
    }
}