首页 / 问题 / 正文

不使用排序进行排序

0 投票
2 回答
1633 浏览
提问于 2025-04-17 20:00

基本上，我想在不使用'sort'的情况下对数字进行排序。我的计划是创建一个新的列表，把每一个最小的数字放进去，比如：

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

这里的List是输入的列表，Min=List[0]，而nList是一个空列表。

我该如何使用双重循环来让它运行呢？

列表操作 排序算法 最小值查找 双重循环

2 个回答

1

你现在做的事情（除了逻辑错误）其实还是在排序，这种排序方法叫做 堆排序，它的时间复杂度是 O(n log n)。

如果你不把列表保持为堆的结构，那么找到最小值的时间就会变成 O(n)，而不是 O(log n)，这样你的排序效率就会变得很差，跟冒泡排序一样，时间复杂度是 O(n^2)。

回答于 2025-04-17 由 Python大师
分享 举报
1

你遇到的第一个问题是，你的代码只遍历了一次列表，因为你写了一个for循环，它只会让你走一遍列表，没有其他的循环。

如果你想让它多次遍历列表，可以在外面再加一个循环。

比如说，因为你每次循环都在从原始列表中删除值，你可以通过在外面加上while List:来一直进行，直到把所有的值都删除掉：

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

不过，这样做其实不会有效果，原因是你原来的逻辑还有其他问题，而不是while循环本身的问题。

首先，明显的问题有：

  1. 你在遍历List的时候同时在删除里面的元素。这是非法的，技术上讲可能会发生各种意外，但实际上会导致你跳过一些元素。

  2. 你把Min初始化为List[0]，尽管这通常不是最小值。这意味着至少在第一次遍历时，你添加的元素顺序会错。

  3. 最终，你会遇到这样的情况：item >= Min对于List中剩下的每个元素都是成立的。那时候会发生什么呢？你什么都不动，就会一直循环下去，什么也不做。

回答于 2025-04-17 由 Python大师
分享 举报

撰写回答