选择排序算法的差异

Question

有人能帮我解释一下，对于最坏的情况，这两种选择类型是否有不同的“大O”符号，还是它们是相同的？非常感谢。

“”选择排序1:该函数使用'find_smallest‘函数

问:在最坏的情况下，selection_sort1是否是O(nlogn)，因为每次执行for循环时，arr的大小都会减少1？“。

def selection_sort1(arr):
    new_arr = []

    for i in range(len(arr)):
        smallest = find_smallest(arr)
        new_arr.append(arr.pop(smallest))

    return new_arr

“”选择排序2:该函数使用'min()‘函数和'remove()’方法。

问:得出selection_sort2函数将运行O(n^2)的结论是否明智？因此，selection_sort1比selection_sort2强？“”

def selection_sort2(arr):
    new_arr = []

    for i in range(len(arr)):
        new_arr.append(min(arr))
        arr.remove(min(arr))

    return new_arr

这个函数由Selection_sort1使用

def find_smallest(arr):
    smallest = arr[0]
    smallest_index = 0

    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i

    return smallest_index

测试用例

arr = [5,2,8,5,1,9,4]
print(selection_sort1(arr))

Answer 1

我认为这是因为选择排序2在for-循环中有更多的进程。