如何使用嵌套的 for 循环重写这个 while 循环？

Question

我遵循了一个带有while循环的算法，但问题的一个参数是我使用嵌套的 for 循环，我不知道该怎么做。这是while循环：i = len(lst)while i > 0:    big = lst.index(max(lst[0:i]))    lst[big], lst[i-1] = lst[i-1], lst[big]    i = i - 1    return lst这是它要回答的问题：输入： [5,1,7,3]首先，找到最大的数，即7。将它与当前位于列表末尾的数字交换，即3. 现在我们有：[5,1,3,7]现在，找到最大的数，不包括7，即5。交换它和倒数第二个数字，即3. 现在我们有：[3,1,5,7]。现在，找到第三大数（不包括前两个数），即3。交换它和倒数第三个数字，即1.输出： [1, 3, 5, 7]

Answer 1

您在算法中看到的是选择排序。这是您提出的第二个解决方案（嵌套for循环）：

def insertion_sort(arr):

    l = len(arr)

    for i in range(l-1, -1, -1):

        m = -10000 # it should be lower than min(arr)

        idx = -1

        for key, val in enumerate(arr[:i+1]):

            if m < val:

                m = val

                idx = key

        if idx != -1:

            arr[i], arr[idx] = arr[idx], arr[i]

    return arr

快速测试：

arr = list(range(10))[::-1]

print(arr)

# prints [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

result = insertion_sort(arr)

print(result)

# prints [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Answer 2

这看起来像一个（相当慢的）排序算法——即冒泡排序。它从列表的末尾迭代lst。然后它在第一个n-1元素中搜索最大值，并将它们与末尾交换。但是，如果最大值已经在末尾，它将失败，因为它将自动max(n-1)与该n值交换。您需要为此添加支票。

因此，乍一看，我不确定是否i在之前定义过，但让我们假设它是在 list 的长度上定义的lst，看起来是这样。所以让我们从外部循环开始 - 因为有一个看起来像是从i0倒计时的 while 循环。这与递增的 for 循环相反，因此我们可以创建一个保留范围：

rev_range = range(0,len(lst))

rev_range.reverse() 

for j in rev_range:

    # perform the sort

我们现在有了用于倒计时 while 循环的外部循环。排序本身向前迭代，直到找到最大值。这是一个前向 for 循环。

# sorting

max_val_so_far_index=lst[j]

# lst[:j-1] gets the first j-1 elements of the list

for k in lst[:j-1]:

    if lst[k] > lst[max_val_so_far_index]:

        max_val_so_far_index = k

# now we have the index of the maximum value

# swap

temp = lst[j]

lst[j] = lst[max_val_so_far_index]

lst[max_val_so_far_index]=temp

让我们把这两个组件放在一起得到：

rev_range = range(0,len(lst))

rev_range.reverse() 

for j in rev_range:

    # perform the sort

    # sorting

    #print j

    max_val_so_far_index=j

    # get the first j items

    for k in range(j):

        if lst[k] > lst[max_val_so_far_index]:

            max_val_so_far_index = k

    # now we have the index of the maximum value

    # swap

    temp = lst[j]

    lst[j] = lst[max_val_so_far_index]

    lst[max_val_so_far_index]=temp

最后lst是排序的。