插入排序实现效率

Question

我在Python中插入排序的方法有效吗？

怎样才能提高效率呢？

def insertion_sort(array):
    sorted_array = []  

    for elem in array:
        insertion_index = len(sorted_array) #insert at end of list by default
        for elem_sorted in sorted_array:
            if elem_sorted > elem:
                insertion_index = sorted_array.index(elem_sorted)
                break
        sorted_array.insert(insertion_index, elem)
    return sorted_array


num_elems = int(input('Number Of Elements?: '))
array = [int(input(f'Enter Number#{i+1}: ')) for i in range(num_elems)]
a = insertion_sort(array)
print(a)

Answer 1

您正在遍历数组元素，一旦发现一个元素大于要插入的元素，就必须再次在元素数组中找到该元素。

        insertion_index = len(sorted_array)
        for elem_sorted in sorted_array:
            if elem_sorted > elem:
                insertion_index = sorted_array.index(elem_sorted)
                break

您可以使用enumerate同时提取元素及其索引：

        insertion_index = len(sorted_array)
        for index, elem_sorted in sorted_array:
            if elem_sorted > elem:
                insertion_index = index
                break

在找到感兴趣的元素时，当您使用for循环和break搜索元素时，如果找不到该元素，则for循环将执行一个可选的else:子句，因此不需要预先设置insertion_index：

        for index, elem_sorted in sorted_array:
            if elem_sorted > elem:
                insertion_index = index
                break
        else:
            insertion_index = len(sorted_array)

最大无效率

sorted_array按顺序排列。您可以使用二进制搜索来查找插入位置O(\log N)，而不是线性搜索O(N)。