使用插入排序从大到小排序列表

Question

我正在尝试创建一个程序，该程序使用插入排序算法从大到小对 10 个数字的随机列表进行排序。也就是说，找到列表中最大的数字并使用 .append 将其添加到新列表中。如果重复此操作直到列表末尾，则新列表将从大到小排序。我已经创建了一个成功创建随机列表的程序，找到列表中最大的数字，并将其添加到新列表中，唯一的问题是我找不到让程序重复 10 次的方法。谢谢！

import random
num_list = []
new_list=[]

for num in range(10):
    num_list.append(random.randrange(0,11))

largest=num_list[0]

for repeat in range(len(num_list)):
    for large in num_list:
        if large>largest:
            largest=large
            new_list.append(largest)

print new_list

请注意，此程序的重点是不使用任何会为我排序列表的函数。

Answer 1

您可以通过在每一步中从未排序列表中删除最大值并将其附加到新列表来实现。它不是很有效，但它相当简单。

new_list = []

# init random list
num_list = [random.randrange(0, 11) for _ in range(10)]

# while condition will evaluate to False 
# only when num_list is empty

while num_list:  
    # find index of maximum item
    max_index = num_list.index(max(num_list)) 

    # remove item with pop() and append to sorted list
    new_list.append(num_list.pop(max_index))

编辑：如果您想避免使用内置函数 max()，您可以使用 reduce() 自行编写。

mx = lambda x: reduce(lambda xs, ys: xs if xs > ys else ys, x)

然后在找到 max_index.

的行中将 max 替换为 mx

使用插入排序从大到小排序列表

Order a list from largest to smallest using insertion sort

python

for-loop

while-loop