我试图以两种不同的方式实现选择排序算法,而我只是想知道这是否被认为是该算法的有效实现。是否也将其视为算法的有效实现,还是有其他更有效的方法?
这是我的实现:
实施尝试#1
def selection_sort(L: List[int]) -> List[int]:
for i in range(len(L) - 1):
j = i
smallest_num = L[i]
while j < len(L) - 1:
if smallest_num > L[j + 1]:
smallest_num = L[j + 1]
j += 1
L[L.index(smallest_num)], L[i] = L[i], L[L.index(smallest_num)]
return L
实施尝试#2
def selection_sort(L: List[int]):
for i in range(len(L) - 1):
j = i
while j < len(L) - 1:
swap_min(L, i)
j += 1
return L
def swap_min(L: List[int], n: int) -> None:
smallet_num = min(L[n:])
sm_indx = L.index(smallet_num)
L[n], L[sm_indx] = L[sm_indx], L[n]
非常感谢!
L.index(smallest_num)
的使用使这些实现均无效。以输入列表[1, 0, 1, 0, 1]
为例,两个实现都以[1, 1, 0, 0, 1]
作为结果,这显然没有正确排序。
您的算法在此输入上不起作用的原因是它包含重复的元素,因此.index
方法并不总是返回您想要的索引;如documentation所说,.index
方法返回给定值首次出现的索引。这并不总是您要查找的事件的索引。有时,该索引在列表的“已排序”部分中,因此您最终将它们交换回不属于它们的位置。
选择排序的正确实现应在列表的未排序部分中搜索最小元素的索引。