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

Question

我正在学习选择排序算法

from typing import List

def 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_index

def 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我看到你的问题之前，我从来没有考虑过关于最小的假设：Ddef sort(arr):&nbsp; &nbsp; for i in range(len(arr)):&nbsp; &nbsp; &nbsp; &nbsp; # we presume a[i] is the smallest one. Then we update by compare it with the rest of the list&nbsp; &nbsp; &nbsp; &nbsp; for j in range(i + 1, len(arr)):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 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])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; swap(arr[i], arr[j])&nbsp; &nbsp; &nbsp; &nbsp; # 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 Listdef find_smallest(arr:List) -> int:&nbsp; &nbsp; smallest = arr[0] #set pivot&nbsp; &nbsp; smallest_index = 0&nbsp; &nbsp; print("presumed smallest {}".format(smallest)) #print presumed&nbsp; &nbsp; for i in range(1, len(arr)):&nbsp; &nbsp; &nbsp; &nbsp; if arr[i] < smallest:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; smallest = arr[i]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; smallest_index = i&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; print("updated smallest {}".format(smallest)) #print updates to smallest&nbsp; &nbsp; return smallest_index结果：find_smallest([7,6,1,3,8,9,0])>>presumed smallest 7updated smallest 6updated smallest 1updated smallest 06