-2

我有一个LinkedList需要排序的（它包含ints），我不知道该怎么做。任何人都可以给我的源代码来对 int Linked List 进行排序吗？

我尝试了我在网上找到的这段代码，但它没有用。

    public void sort(LinkedList sortlist)
{
    //Enter loop only if there are elements in list
    boolean swapped = (head != null);

    // Only continue loop if a swap is made
    while (swapped)
    {
        swapped = false;

        // Maintain pointers
        Node curr = head;
        Node next = curr.link;
        Node prev = null;

        // Cannot swap last element with its next
        while (next != null)
        {
            // swap if items in wrong order
            if (curr.data>next.data)
            {
                // notify loop to do one more pass
                swapped = true;

                // swap elements (swapping head in special case
                if (curr == head)
                {
                    head = next;
                    Node temp = next.link;
                    next.link = curr;
                    curr.link = temp;
                    curr = head;
                }
                else
                {
                    prev.link = curr.link;
                    curr.link = next.link;
                    next.link = curr;
                    curr = next;
                }
            }

            // move to next element
            prev = curr;
            curr = curr.link;
            next = curr.link;
        }
    }
}
4

2 回答 2

3

斯坦福大学 CS106B 课程的本讲义中提供了链表上合并排序的C++ 实现。它运行时间为 O(n log n)，非常好。

有关其他方法的调查，请查看有关如何对链表进行排序的旧 SO 答案。那里没有代码，但是很好地描述了如何使现有想法适应链表。

希望这可以帮助！

于 2013-01-11T03:25:55.993 回答
0

合并排序和快速排序可用于对链接列表（平均 O(n.long)）进行就地排序。此外，如果您的数字是整数，则有一种基数排序的变体，它可以工作 O(n) 并且它已经到位。所以你不满足将链表转换为数组。

以下是 STL 中的实施信息：http ://www.cplusplus.com/reference/list/list/sort/

于 2013-02-02T07:32:32.117 回答