时间戳

首页 > 解决方案 > Python：设置递归限制减慢排序程序

python - Python：设置递归限制减慢排序程序

问题描述

我正在做一个程序，比较不同的排序算法：插入排序、冒泡排序和快速排序。当输入是至少 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)，但它大大减慢了快速排序算法。例如对于列表中的 10 000 个元素，快速排序比插入排序慢：

对包含 10000 个元素的列表进行插入排序：3.238

对 10000 个元素的列表进行冒泡排序耗时：5.618 秒

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

此外，如果我只运行没有插入排序和气泡排序的快速排序算法，那么它工作正常。它应该尽可能快：

快速排序 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))

标签： pythonsortingrecursionquicksort

解决方案

问题是您在前两种排序中对列表进行排序，因此当它到达快速排序时它已经排序

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

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

您将需要从原始订单复制列表排序。

import copy

lst_b = copy.deepcopy(lst)
lst_q = copy.deepcopy(lst)

insertionSort(lst)
bubbleSort(lst_b)
quickSort(lst_q)

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

推荐阅读