python - 我在 python 中的排序算法有时会在运行时卡住，有人可以看一下吗？

Question

基本上我一直在尝试的是，我从未排序的列表中挑选出最小的和最大的，然后将它们附加到新列表中，然后从旧的未排序列表中弹出最小的和最大的并执行该过程一遍又一遍，直到我得到一个排序列表。请看一下我的代码。

import random
import time

stack = [] #sorted list
numbersarray = [] #unsorted list

usersize = int(input("How many digits do you want in your array? ")) #numberofinputs
limit = 0
counter = 0


while limit <= usersize:
    numbersarray.append(random.randint(0,20)) #randomly input numbers into array
    limit = limit + 1

print(numbersarray) #prints the current unsorted array
start_time = time.time() #starts clock

subtractor = 0 #used later in code for changing index
while len(numbersarray) != 0:
    i = 0
    largest = numbersarray[i]
    size = len(numbersarray) -1
    smallest = numbersarray[i]

while (i < len(numbersarray)): 
    if numbersarray[i] >= largest:
        largest = numbersarray[i]
        index = i
    elif numbersarray[i] <= smallest:
        smallest = numbersarray[i]
        indextwo = i
    i = i+1

if (len(numbersarray) == 1): #this checks if there's only 1 number left.
    entry = int(stacksize/2 + 1)
    stack.insert(entry,numbersarray[0])
    break
else:
    if indextwo > index:
        numbersarray.pop(indextwo)
        numbersarray.pop(index)
    elif index > indextwo:
        numbersarray.pop(index)
        numbersarray.pop(indextwo)

stacksize = len(stack)
if stacksize == 0:
    stack.append(smallest)
    stack.append(largest)
elif stacksize != 0:
    stack.insert(stacksize-subtractor,largest) #the subtractor is dynamically changing the index of insertion.
    stack.insert(0+subtractor,smallest)
subtractor = subtractor + 1

print(stack)
print("--- %s seconds ---" % (time.time() - start_time))

Answer 1

您有一个双重嵌套的 while 循环，您在其中扫描整个数组以查找 max 和 min，然后继续处理 .pop 元素从列表中的任意位置。

考虑到 pop 对于不在列表末尾的项目具有 O(N) 的复杂性；您的方法效率非常低，如果 usersize 的值很大，将会传递/卡住。这就是为什么，我猜，当 usersize 很大时，标题中的“有时”会发生。

简而言之，在这种情况下，您需要找到更好的算法来解决您的问题。