这是选择排序算法的有效实现吗?

问题描述 投票:0回答:1

我试图以两种不同的方式实现选择排序算法,而我只是想知道这是否被认为是该算法的有效实现。是否也将其视为算法的有效实现,还是有其他更有效的方法?

这是我的实现:

实施尝试#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]

非常感谢!

python algorithm testing
1个回答
0
投票

L.index(smallest_num)的使用使这些实现均无效。以输入列表[1, 0, 1, 0, 1]为例,两个实现都以[1, 1, 0, 0, 1]作为结果,这显然没有正确排序。

您的算法在此输入上不起作用的原因是它包含重复的元素,因此.index方法并不总是返回您想要的索引;如documentation所说,.index方法返回给定值首次出现的索引。这并不总是您要查找的事件的索引。有时,该索引在列表的“已排序”部分中,因此您最终将它们交换回不属于它们的位置。

选择排序的正确实现应在列表的未排序部分中搜索最小元素的索引。

© www.soinside.com 2019 - 2024. All rights reserved.