我写了一个快速选择算法如下:
def partition(arr):
pvt = 0
for i in range(len(arr) - 1):
if arr[i] < arr[-1]:
arr[i], arr[pvt] = arr[pvt], arr[i] # mv smaller elements before pvt
pvt += 1
arr[-1], arr[pvt] = arr[pvt], arr[-1]
return pvt
def quickselect(k, arr):
p = partition(arr)
while k != p:
p = partition(arr[:p]) if k < p else partition(arr[p:])
return arr[k]
我打算做的是在复杂度为 O(n) 的 arr 中找到第 k 个元素。但是当我完成编码时，我发现 arr[:p] 实际上传递的是一个副本而不是原始列表的一部分，这不会使递归分区正常工作。据我所知，pandas Series slice 实际上做了我想要的。如果我将 arr 作为 pd.Series 传递，它似乎可以正常工作。但是有没有更原生的方法来传递 python 列表 arr[:p] 的原始切片？
请您参考如下方法:
arr[:p] 是一个拷贝，所以不拷贝就没办法传递。
正如您已经发现的，您可以使用不同类型的“ View 切片”—memoryview、np.array、pd.Series 等
或者您可以将整个列表和切片信息一起传递，如下所示:
def partition(arr, start, stop):
pvt = 0
for i in range(start, stop - 1):
if arr[i] < arr[stop-1]:
arr[i], arr[pvt] = arr[pvt], arr[i] # mv smaller elements before pvt
pvt += 1
arr[stop-1], arr[pvt] = arr[pvt], arr[stop-1]
return pvt
def quickselect(k, arr, start=None, stop=None):
if start is None: start = 0
if stop is None: stop = len(arr)
p = partition(arr, start, stop)
while k != p:
p = partition(arr, start, p) if k < p else partition(arr, p, stop)
return arr[k]
或者您可以编写一个简单的包装器，它包含列表、开始和停止值，并通过适当的转发实现 collections.abc.Sequence(或 MutableSequence)。这需要更多的前期工作，但它可能会使您编写的其他代码更具可读性。
您可以找到可变和不可变切片 View 的简单版本 here .它没有像我希望的那样经过全面测试，但它似乎适用于您的 quickselect。 (当然，线性而不是二次工作的成本可能被为每个切片构建包装对象的常数乘数所淹没，直到你得到适当大小的列表......)
