Python:设置递归限制会减慢排序程序的速度

Question

我正在做一个程序，它比较不同的排序算法：插入排序、气泡排序和快速排序。当输入是至少1000个元素的列表时，程序会抛出错误。

File "/Users/karol/PycharmProjects/Algorytmy6/main.py", line 52, in quickSort
return quickSort(less) + equal + quickSort(greater)
[Previous line repeated 995 more times]
File "/Users/karol/PycharmProjects/Algorytmy6/main.py", line 43, in quickSort
if len(list) > 1:
RecursionError: maximum recursion depth exceeded while calling a Python object

我试图通过sys.setrecursionlimit(sizeOfList+1)设置递归限制，但它大大降低了快速排序算法的速度。例如，对于列表中的10000个元素，快速排序比插入排序慢：

插入排序10000个元素的列表花费：3.238

气泡排序10000个元素的列表耗时：5.618s

快速排序10000个元素的列表耗时：4.239秒

此外，如果我只运行quickSort算法，而不运行insertionSort和bubbleSort，那么它运行得很好。它的速度和它应该的一样快：

快速排序10000个元素的列表耗时：0.077秒

我需要真正的快速排序时间，因为该程序是为了将其与其他排序算法进行比较。

这是我的代码：

import random, time
def insertionSort(list):
startTime = time.time()
for i in range(len(list)):
min = list[i]
for j in range(i, len(list)):
if list[j] <= min:
min = list[j]
index = j
list[index] = list[i]
list[i] = min
elapsedTime = round(time.time() - startTime, 3)
print("Insertion sorting a list of {} elements took: {} s".format(len(list), elapsedTime))
return list
def bubbleSort(list):
startTime = time.time()
n = len(list) - 1
for j in range(len(list)):
for i in range(n-j):
if list[i] > list[i+1]:
temp = list[i]
list[i] = list[i+1]
list[i+1] = temp

elapsedTime = round(time.time() - startTime, 3)
print("Bubble sorting a list of {} elements took: {} s".format(len(list), elapsedTime))
return list
def quickSort(list):
less = []
equal = []
greater = []
if len(list) > 1:
pivot = list[0]
for x in list:
if x < pivot:
less.append(x)
elif x == pivot:
equal.append(x)
elif x > pivot:
greater.append(x)
return quickSort(less) + equal + quickSort(greater)
else:
return list

size = 10000
list = [0]*size
for i in range(size):
list[i] = random.randint(1, size)
insertionSort(list)
bubbleSort(list)
startTime = time.time()
quickSort(list)
elapsedTime = round(time.time() - startTime, 3)
print("Quick sorting a list of {} elements took: {} s".format(len(list), elapsedTime))

Answer 1

问题是，您按前两种排序方式对列表进行排序，因此当列表到达快速排序时，它就已经排序了

insertionSort(lst)
bubbleSort(lst)
quickSort(lst)

对同一个列表排序3次，但它已经在第一次insertionSort之后排序。

您需要从原始顺序复制列表排序。

import copy
lst_b = copy.deepcopy(lst)
lst_q = copy.deepcopy(lst)
insertionSort(lst)
bubbleSort(lst_b)
quickSort(lst_q)

您在原始代码中看到quickSort问题的原因是，当列表已经排序时，排序列表会导致二次时间。