Python 在常量空间中排序 O(1)

Question

我想使用

Python 3

就地 对列表进行排序，并且没有额外空间。

据我所知，Python 使用

sorted(myList)

对列表进行排序，这会创建一个新的排序数组，显然会占用 O(N) 额外空间。或者使用

myList.sort()

，它使用 Timsort，它的最坏情况空间复杂度也为 O(N)。

我搜索了文档，但没有找到任何恒定空间算法的内置函数（选择排序、插入排序、希尔排序、堆排序、鸡尾酒排序等）

我知道我可以找到这些算法的实现，但内置的手动优化实现是我希望找到的最好的。

如有任何建议，我们将不胜感激。

Answer 1

您最好的选择是使用堆排序，它既具有合理的时间效率（具有 O(n log n) 时间复杂度）又具有空间效率（具有保证的 O(1) 空间复杂度）。

虽然Python有一个内置模块

heapq

实现了二叉堆，但它只导出最小堆的函数，这不适合就地排序，因为我们想要交换较大的排序项，而不是最后的排序项。其他方式。

幸运的是，为了满足

heapq.merge

在反向模式下的需求，

heapq

实际上还实现了一个具有非导出函数的最大堆，其中包括

_heapify_max

，一个

heapify

的等效函数，可将列表转换为最大堆，以及

_siftup_max

，一个冒泡较大子堆的函数 给定的起始位置向上（以及该孩子的孩子等），直到碰到一片叶子。

但是，

heapq._siftup_max

函数不将结束位置作为参数，这是限制堆大小以保留已排序项目到列表末尾的必要条件。因此，为了解决缺少结束位置参数的问题，我们可以将

memoryview

的切片

array.array

传递给它，因为您在评论中提到您所拥有的“通常是始终适合的整数”在内存中”，它可以轻松加载为

array

类型（64 位有符号整数）的

'q'

。

但是，

heapq

模块将尝试从其 C 实现导入

_heapq

（如果可用），并且

_heapq._heapify_max

将专门验证参数为

list

并拒绝

array

。

heapq._heapify_max

的 Python 实现没有这个限制，因此要导入它，我们需要首先自己导入

_heapq

，然后从

_heapify_max

模块对象中删除

_heapq

，以便

heapq

成为

_heapify_max

当我们导入时不会被覆盖

heapq

:

import sys
import _heapq
del sys.modules['_heapq']._heapify_max
from heapq import _heapify_max, _siftup_max

因此，以下是如何使用

heapq

的内置函数执行堆排序，首先使用

_heapify_max

堆化数组，然后迭代地交换根部的最大数字与末尾的叶子并使用

_siftup_max 

将其筛选到其所有子级都较小的位置：

def heapsort(arr):
    _heapify_max(arr)
    view = memoryview(arr)
    for size in reversed(range(1, len(arr))):
        view[0], view[size] = view[size], view[0]
        _siftup_max(view[:size], 0)

这样：

arr = array('q', [1, 5, 0, 7, 3, 6, 9, 8, 2, 4])
heapsort(arr)
print(arr)

输出：

array('q', [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

演示这里

最后，请注意，如果您希望能够对任何列表进行排序，您始终可以从头开始实现堆排序：

def heapsort(lst):
    for child in range(1, length := len(lst)):
        while lst[child] > lst[parent := int((child - 1) / 2)]:
            lst[child], lst[child := parent] = lst[parent], lst[child]
    for size in range(length - 1, 0, -1):
        lst[child := 0], lst[size] = lst[size], lst[0]
        while (parent := child) < size:
            if (child := 2 * parent + 1) < size - 1 and lst[child] < lst[child + 1]:
                child += 1
            if child < size and lst[parent] < lst[child]:
                lst[parent], lst[child] = lst[child], lst[parent]