python - 无排序排序

Question

基本上，我想在不使用“排序”的情况下对数字进行排序。我打算做的是创建一个新列表并将每个 Min 数字放入其中，例如：

for item in List:
    if item < (Min):
        Min = item
        nList.append(Min)
        List.remove(Min)

其中List是输入列表，Min=List[0] and nList =[]

如何使用双循环来保持运行？

score 1 · Accepted Answer

您正在做的事情（除了逻辑错误）仍在排序 - 它被称为堆排序，这需要O(n log n)时间。

如果您不将列表保留为堆，则您找到的最小值将O(n)不是O(log n)，并且您的排序将渐近运行，与冒泡排序一样糟糕 - O(n^2)。

score 1 · Accepted Answer

您的第一个问题是它只运行一次列表，因为……您编写了一个for显式运行一次列表的循环，而没有其他循环。

如果您希望它重复遍历列表，请在其周围放置另一个循环。

例如，由于您每次通过循环都从原始列表中删除值，因此您可以继续进行，直到您将它们全部删除，方法是添加while List:为外部循环：

while List:
    for item in List:
        if item < (Min):
            Min = item
            nList.append(Min)
            List.remove(Min)

这实际上不会按原样工作，但这是因为原始逻辑中的其他缺陷，而不是while循环中的任何新内容。

第一个明显的问题是：

2 回答 2