我在python中的排序算法有时会在运行时冻结,有人能看一下吗?

2024-03-28 09:45:28 发布

您现在位置:Python中文网/ 问答频道 /正文

基本上我一直在尝试的是,我从未排序的列表中挑选最小和最大的,然后将它们附加到一个新的列表中,然后从旧的未排序列表中弹出最小和最大的,然后一遍又一遍地做这个过程,直到得到一个已排序的列表。请看一下我的密码

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))

Tags: 列表indexleniftime排序stackpop
1条回答
网友
1楼 · 发布于 2024-03-28 09:45:28

有一个双重嵌套的while循环,在该循环中扫描整个数组的maxmin,然后从任意位置的列表中转到.pop元素

考虑到pop对于不在列表末尾的项具有O(N)复杂性;您的方法效率很低,对于usersize的大值,它将被传递/冻结。这就是为什么,我猜,当usersize很大时,标题中的“有时”会出现

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

相关问题 更多 >