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

Question

Python 3 我想使用in place对列表进行排序，没有额外的空间。

据我所知，Python 使用 来对列表进行排序sorted(myList)，这会创建一个新的排序数组，显然会占用 O(N) 的额外空间。或者使用myList.sort()which 使用Timsort，它的最坏情况空间复杂度也为 O(N)。

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

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

任何建议表示赞赏。

Answer 1

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

\n

虽然 Python 有一个实现二叉堆的内置模块heapq，但它仅导出执行就地堆排序所需的两个函数之一heapify，它将列表转换为最小堆；另一个必要的函数 ，_siftup是一个使给定起始位置的较小子项冒泡的函数（以及该子项的子项，依此类推）直到碰到叶子，该函数未导出。

\n

如果没有_siftup，只能通过将堆中的最小值弹出到记录的新列表中来执行堆排序，这会消耗O(n)的空间复杂度：

\n

\n

堆排序可以通过将所有值压入堆然后每次弹出最小值来实现：

\n

>>> def heapsort(iterable):\n...     h = []\n...     for value in iterable:\n...         heappush(h, value)\n...     return [heappop(h) for i in range(len(h))]\n... \n>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])\n[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n

\n

\n

更重要的是，heapify将列表转换为最小堆，这对于就地排序来说并不理想，因为我们希望在末尾交换较大的排序项，而不是相反。引用自heapq\的文档：

\n

\n

我们的 pop 方法返回最小的项，而不是最大的项（在教科书中称为 a\n\xe2\x80\x9cmin heap\xe2\x80\x9d；a \xe2\x80\x9cmax heap\xe2\x80\x9d 在文本，因为\n它适合就地排序）。

\n

\n

heapq.merge幸运的是，为了满足反向模式的需要，heapq实际上还实现了带有其他未导出函数的最大堆，包括 的_heapify_max最大堆版本heapify和_siftup_max的最大堆版本_siftup。

\n

但是，该heapq._siftup_max函数不将结束位置作为参数，这是限制堆大小以保留已排序项目到列表末尾的必要条件。因此，为了解决缺少结束位置参数的问题，同时保持O(1)memoryview空间复杂度，我们可以将an 的切片传递给它，array.array因为您在评论中提到您所拥有的是“通常可以始终适合的整数”内存”，它可以轻松地作为arrayof 类型\'q\'（64 位有符号整数）加载。

\n

但是，该heapq模块将尝试从其 C 实现导入 ，_heapq如果可用，并且_heapq._heapify_max会专门验证参数为 alist并拒绝array。Python 实现heapq._heapify_max没有这个限制，因此要导入它，我们需要首先导入_heapq自己并_heapify_max从_heapq模块对象中删除，以便导入时不会被heapq覆盖：_heapify_maxheapq

\n

import sys\nimport _heapq\ndel sys.modules[\'_heapq\']._heapify_max\nfrom heapq import _heapify_max, _siftup_max\n

\n

因此，以下是如何使用heapq内置函数执行堆排序，首先使用 堆化数组_heapify_max，然后迭代地交换根部的最大数字与末尾的叶子，并使用_siftup_max筛选它到它的所有子项都较小：

\n

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

\n

或者要使用最小堆执行堆排序，您最终必须反转结果：

\n

import sys\nimport _heapq\ndel sys.modules[\'_heapq\'].heapify\nfrom heapq import heapify, _siftup\nfrom array import array\n\ndef heapsort(arr):\n    view = memoryview(arr)\n    heapify(view)\n    for size in reversed(range(1, len(arr))):\n        view[0], view[size] = view[size], view[0]\n        _siftup(view[:size], 0)\n    arr.reverse()\n

\n

以便：

\n

arr = array(\'q\', [1, 5, 0, 7, 3, 6, 9, 8, 2, 4])\nheapsort(arr)\nprint(arr)\n

\n

输出：

\n

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

\n

此处使用最大堆和最小堆进行演示

\n

或者，正如 @KellyBundy 在评论中指出的那样，我们可以通过heapq._siftup使用代理对象来解决 \ 缺少结束位置参数的问题，该代理对象size在切片时通过人为设置的属性限制堆的大小，并将该属性报告为长度当它的堆__len__。

\n

除了允许任何列表作为输入之外，与此方法相比的额外好处memoryview是我们不需要_heapq先导入即可删除heapify，因为我们现在可以将实际列表传递给它：

\n

from heapq import heapify, _siftup\n\nclass heapsort:\n    def __init__(self, lst):\n        self.list = lst\n        heapify(lst)\n        for self.size in reversed(range(1, len(lst))):\n            lst[0], lst[self.size] = lst[self.size], lst[0]\n            _siftup(self, 0)\n        lst.reverse()\n\n    def __len__(self):\n        return self.size\n\n    def __getitem__(self, index):\n        return self.list[index]\n\n    def __setitem__(self, index, value):\n        self.list[index] = value\n

\n

此处使用代理对象进行演示

\n

同样，我们可以使用代理对象来使heappop基于堆排序就地工作，方法是使代理对象仅返回堆末尾的项目，而不是在弹出时实际将其删除。

\n

然而，在这种情况下， 的 C 实现heappop不仅会将代理对象验证为一个list对象（可以通过使代理对象继承自 来补救list），而且还直接将其长度作为 C 属性访问，而不是调用我们的重写__len__方法，所以我们必须删除 C 实现来调用 Python 版本。

\n

这种方法的优点是坚持使用公开可用的 API，因此最不容易受到实现更改的影响heapq：

\n

import sys\nimport _heapq\ndel sys.modules[\'_heapq\'].heappop\nfrom heapq import heapify, heappop\n\nclass heapsort:\n    def __init__(self, lst):\n        heapify(lst)\n        self.list = lst\n        for self.size in range(len(lst), 0, -1):\n            lst[self.size - 1] = heappop(self)\n        lst.reverse()\n\n    def __len__(self):\n        return self.size\n\n    def __getitem__(self, index):\n        return self.list[index]\n\n    def __setitem__(self, index, value):\n        self.list[index] = value\n\n    def pop(self):\n        return self.list[self.size - 1]\n

\n

此处演示heappop

\n

最后，请注意，在极不可能的情况下，您总是可以从头开始实现堆排序，这种情况heapq完全改变了其实现，以至于上述方法都不起作用（同样，极不可能，特别是对于heappop基于 - 的解决方案）：

\n

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

\n