双链表冒泡排序

Question

void sortTrain(TrainCar* head, bool ascending)
{
    TrainCar* current = head;
    int count = 1;
    int size = (getlength(head));
    if (ascending == 1)
    {
        for(int i = 0; i < size-1; i++)
        {
            while(current->next)
            {
                if((current->load) > ((current->next)->load))
                {
                    swapCar(head,count,count+1);
                }
                count++;
                current = current->next;
            }
        }
    }

    if (ascending == 0)
    {
        for(int i = 0; i < size-1; i++)
        {
            while(current->next)
            {
                if((current->load) < ((current->next)->load))
                {
                    swapCar(head,count,count+1);
                }
                count++;
                current = current->next;
            }
        }
    }
}

有人帮我解决问题吗？我不知道如何改进它。或者任何其他代码可以做同样的结果？当 bool ascending 为真时升序，否则，做降序。

Answer 1

您发布的代码中的主要错误是您没有在每次外循环迭代后重置 current 和 count，即尝试以下操作：

// ...

if (ascending == 1)
{
    for (int i = 0; i < size-1; i++)
    {
        TrainCar* current = head;
        int count = 0;
        while (current->next)
        {
            if ((current->load) > ((current->next)->load))
            {
                swapCar(head, count, count + 1);
            }
            count++;
            current = current->next;
        }
    }
}

// ...

如果 swapCar 使用从零开始的索引，上面的方法应该有效（我也改变了它，这样 count 被初始化为零而不是一个：永远不要在 C 中使用从 1 开始的索引或 C++；这样做只会让人感到困惑）。

但是，将 swapCar 实现为采用索引是一个糟糕的设计。每次调用 swapCar 都将在 O(n) 时间内执行，如果您知道那意味着什么。您已经有 current 和 current->next 坐在那里：只需交换它们的负载值，然后您甚至根本不需要维护 count 变量。

双链表冒泡排序

Bubble sort in double linked list

c++

bubble-sort

visual-studio

c++11