假设一个值作为初始值，在循环中更新它的值

Question

我正在学习选择排序算法from typing import Listdef find_smallest(arr:List) -> int:    smallest = arr[0] #set pivot    smallest_index = 0    for i in range(1, len(arr)):        if arr[i] < smallest:            smallest = arr[i]            smallest_index = i    return smallest_indexdef selection_sort(arr) -> List:    new_arr = []    for i in range(len(arr)):        smallest = find_smallest(arr)        new_arr.append(arr.pop(smallest))    return new_arr我对这个函数很好奇find_smallest，它首先假定 arr[0] 是最小的并启动循环。我知道完整的代码叫做选择排序算法，在循环中假设并更新其值如何，是否有术语？

Answer 1

我认为bubble sort是答案。在bubble loop我看到你的问题之前，我从来没有考虑过关于最小的假设：D

def sort(arr):

    for i in range(len(arr)):

        # we presume a[i] is the smallest one. Then we update by compare it with the rest of the list

        for j in range(i + 1, len(arr)):

            if arr[i] > arr[j]: # if our assumption is wrong (arr[i] is not the smallest), update it with arr[j] (which is smaller than arr[i])

                swap(arr[i], arr[j])

        # After this `for j` loop, arr[i] will be the smallest value of the list

Answer 2

不。它没有术语，不像快速排序，我们选择一个枢轴并比较元素。超出主题，但关于选择排序的一个有趣事实是

选择排序的好处是它永远不会超过 O(n) 次交换，并且在内存写入是一项昂贵的操作时很有用。

Answer 3

它假定列表的第一个索引是最小值，并向下运行列表以查看是否有任何较小的值，当它确实找到较小的值时，它更新smallest，它这样做直到列表的末尾为了确保找到整个列表中的最小值，在您提供的示例中，它返回列表中最小值的索引。

我添加了 2 个print语句，它们应该让您了解它的工作原理：

from typing import List

def find_smallest(arr:List) -> int:

    smallest = arr[0] #set pivot

    smallest_index = 0

    print("presumed smallest {}".format(smallest)) #print presumed

    for i in range(1, len(arr)):

        if arr[i] < smallest:

            smallest = arr[i]

            smallest_index = i

            print("updated smallest {}".format(smallest)) #print updates to smallest

    return smallest_index

结果：

find_smallest([7,6,1,3,8,9,0])

>>presumed smallest 7

updated smallest 6

updated smallest 1

updated smallest 0

6