c++ - 双向链表冒泡排序，反向方法现已失效

Question

所以我最近更新了我的 Bubblesort(按字母顺序排序)以使用链表。

虽然现在我以前的工作反向方法打破了列表。 (如果我不先进行单列表冒泡排序，以前就可以工作)

冒泡排序和交换。

void bubbleSort() {
    City *temp = NULL;
    City *current = head;
    while (current != NULL) { //for the rest in list
        if (current->getName().compare(current->next->getName()) > 0) { //compare distance
            if (current == head) {
                head = current->next;
            }
            swap(current, current->next);
        }
        current = current->next;
    }
}

交换

void swap(City* i, City* j) {
    if (i->previous)  i->previous->next = j;
    if (j->previous)  j->previous->next = i;
    if (i->next) i->next->previous = j;
    if (j->next) j->next->previous = i;
    City* temp;
    temp = i->previous;
    i->previous = j->previous;
    j->previous = temp;
    temp = i->next;
    i->next = j->next;
    j->next = temp;
}

这是现在损坏的反向列表。

void reverseList() {
    City *temp = NULL;
    City *current = head;

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

    }
    if (temp != NULL) {
        head = temp->previous;
    }
}

问题我在冒泡排序中漏掉了哪些打破列表的东西？

Answer 1

一个错误是您的冒泡排序实现。它应该对数据进行多次传递，因为冒泡排序具有 O(n*n) 复杂性，其中 n 是要排序的项目数。

换句话说，您需要在bubbleSort 中执行while 循环，直到检测到数据已排序。这可以通过使用仅在 swap 发生时设置的 bool 标志然后测试该标志来完成，或者只是让 n 传递数据。