对整数链表进行排序

Question

我有一个LinkedList需要排序(它包含int s)，我不知道如何做到这一点。谁能给我的源代码排序一个int链表?

我尝试了这段我在网上找到的代码，但它不起作用。

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

Answer 1

斯坦福CS106B课程的讲义中给出了链表归并排序的c++实现。它的运行时间为O(n log n)，这是非常好的。

有关其他方法的调查，请查看关于如何排序链表的旧SO答案。这里没有代码，但是有很好的描述了如何将现有的想法应用于链表。

希望这对你有帮助!

Answer 2

归并排序和快速排序可用于对链表(平均O(n.long))进行排序。此外，如果您的数字是整数，则有一种基数排序的变化，其工作时间为O(n)，并且它是适当的。因此，您不需要将链接列表转换为数组。

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