具有快速排序样式的快速选择算法

Question

我正在尝试编写最佳算法以选择列表中较大的第 i 个元素。 例如，如果数组 = [4,3,5,7] 并且我搜索第二个，则该函数将返回 4。

我假设列表在这里只有不同的数字

问题是这样的：

该函数有时会返回 None。

这是我的代码(我认为第一个函数运行良好(。

from random import shuffle
def partition(array, leftend, rightend, pivot):
""" I tested this one and it should work fine """
i = leftend
pivotindex = array.index(pivot)  # only works if all values in array unique
array[pivotindex] = array[leftend]
array[leftend] = pivot
for j in range(leftend+1, rightend):
if array[j] < pivot:
temp = array[j]
array[j] = array[i]
array[i] = temp
i += 1
pivotindex = array.index(pivot)  # only works if all values in array unique
leftendval = array[pivotindex]   # Take the value of the pivot
array[pivotindex] = array[i]
array[i] = leftendval
return array
def RSelect(array, n, statistic_order):
""" list * int * int
statistic_order = the i th element i'm searching for """
new_array = []                  # is used at the end of the function
if n == 1:
return array[0]
array_temp = array              # Allows to have a shuffled list and
shuffle(array_temp)
pivot = array_temp[0]           # Allows to have a random pivot
partition(array,0,n,pivot)
j = array.index(pivot)

if j == statistic_order:
return pivot

elif j > statistic_order:
for k in range(0,j):
new_array.append(array[k])
RSelect(new_array,j,statistic_order)

elif j < statistic_order:
for k in range(j+1,n):
new_array.append(array[k])
RSelect(new_array,(n-j)-1,statistic_order-j)

Answer 1

嗯，有几件事是错误的：

• 在每种情况下，您都需要以递归方法返回结果！
• 当 j ！

我还更改了一些内容，例如无用的参数，或者可以使用切片编写的循环。

这是最终代码，请检查更改以确保您理解它。

RSelect ：

def RSelect(array, statistic_order):
""" list * int * int
statistic_order = the i th element i'm searching for """
n = len(array)
if n == 1:
return array[0]
array_temp = array              # Allows to have a shuffled list and
shuffle(array_temp)
pivot = array_temp[0]           # Allows to have a random pivot
array = partition(array,0,n,pivot)  # Changes here, does not impact the result, but for readability
j = array.index(pivot)
# print(array, j, statistic_order, end = 't')
if j == statistic_order:
return pivot
elif j > statistic_order:
assert j > 0
# print((array[0:j]), pivot)
return RSelect(array[0:j],statistic_order)  # Changes here : return
elif j < statistic_order:
assert j+1 < n
# print(pivot, (array[j+1:n]))
return RSelect(array[j+1:n],statistic_order-j-1)  # Changes here : return, -j-1

主要：

if __name__ == "__main__":
from sys import argv
if len(argv) > 1:
n = int(argv[1])
arr = [2, 1, 3, 5, 4]
print(RSelect(arr[:], n))

为此目的，O(n( 中也存在另一种算法：请参阅此

编辑：更正错别字和更正复杂性

Answer 2

代码工作正常，但结果仍然从 0 开始。 例如，如果 arr = [2,3,5,6] 并且我要求 RSelect(arr，4,2(，则答案将是 5 而不是 3。我不知道为什么。

以下是更新的代码：

from random import shuffle
def partition(array, leftend, rightend, pivot):
i = leftend
pivotindex = array.index(pivot)  # only works if all values in array unique
array[pivotindex] = array[leftend]
array[leftend] = pivot
for j in range(leftend+1, rightend):
if array[j] < pivot:
temp = array[j]
array[j] = array[i]
array[i] = temp
i += 1
pivotindex = array.index(pivot)  # only works if all values in array unique
leftendval = array[pivotindex]   # Take the value of the pivot
array[pivotindex] = array[i]
array[i] = leftendval

def RSelect(array, n, statistic_order):
""" list * int * int
statistic_order = the i th element i'm searching for """
if n == 1:
return array[0]
array_temp = array              # Allows to have a shuffled list
shuffle(array_temp)
pivot = array_temp[0]           # Allows to have a random pivot
partition(array,0,n,pivot)
j = array.index(pivot)

if j == statistic_order:
return pivot

elif j > statistic_order:
return RSelect(array[0:j],j,statistic_order)

elif j < statistic_order:
return RSelect(array[j+1:n],(n-j)-1,statistic_order-j-1)