c++ - 如何在恒定空间中对单链表进行排序？

Question

我有一个单链表，由于内存限制，我需要在恒定空间中对其进行排序（换句话说，不应使用与列表中项目数成正比的额外空间）。

链表的结构是：

• head.item=您要排序的有效负载；和
• head.next= 下一项。

在我建立另一个列表的地方，我需要在原地完成对恒定空间折扣解决方案的要求。

我怎样才能做到这一点？

Answer 1

在常量空间中对链表进行排序很容易，您只需调整指针即可。最简单的方法是使用只交换相邻元素的排序算法。我将提供冒泡排序，只是因为您对效率没有要求：

# Enter loop only if there are elements in list.

swapped = (head <> null)
while swapped:
    # Only continue loop if a swap is made.

    swapped = false

    # Maintain pointers.

    curr = head
    next = curr.next
    prev = null

    # Cannot swap last element with its next.

    while next <> null:
        # Swap if items in wrong order.

        if curr.item > next.item:
            # Notify loop to do one more pass.

            swapped = true

            # Swap elements (swapping head is special case).

            if curr == head:
                head = next
                temp = next.next
                next.next = curr
                curr.next = temp
                curr = head
            else:
                prev.next = curr.next
                curr.next = next.next
                next.next = curr
                curr = next
            endif
        endif

        # Move to next element.

        prev = curr
        curr = curr.next
        next = curr.next
    endwhile
endwhile

Answer 2

几种方法：

• 在列表上使用冒泡排序，如果列表很小，这应该足够快
• 将列表复制到数组并使用堆排序或快速排序，然后将其复制回来
• 在列表中使用 bogosort。最好的案例复杂度是O(n)它应该非常快*

*请注意，预期的运行时复杂度是O(n*n!)

Answer 3

对于链表的就地排序，我建议合并排序。它是稳定的，并且在 NlgN 时间内运行。