Python Quicksort运行时错误:cmp中超出最大递归深度

Question

我正在编写一个程序,它将读取包含5,163个名称的文本文件.(文字文件可以在这里看到)

然后我想将名称存储到名为"names"的列表中,之后,我根据名称包含的字母数量对列表进行排序,较短的名称位于列表的开头,较长的名称位于结尾.

我使用quicksort对列表进行排序,但是当我运行它时,它会显示以下错误:

C:\Python27\python.exe C:/Users/Lenovo/Desktop/Anagrams/Main.py
Traceback (most recent call last):
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 25, in <module>
    names = quicksort(names)
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 8, in quicksort
    greater = quicksort([x for x in list[1:] if not lessThan(x, pivot)])
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 7, in quicksort
    lesser = quicksort([x for x in list[1:] if lessThan(x, pivot)])
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 8, in quicksort
    greater = quicksort([x for x in list[1:] if not lessThan(x, pivot)])
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 7, in quicksort
    lesser = quicksort([x for x in list[1:] if lessThan(x, pivot)])
# [.... many lines elided ...]
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 8, in quicksort
    greater = quicksort([x for x in list[1:] if not lessThan(x, pivot)])
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 8, in quicksort
    greater = quicksort([x for x in list[1:] if not lessThan(x, pivot)])
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 7, in quicksort
    lesser = quicksort([x for x in list[1:] if lessThan(x, pivot)])
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 3, in quicksort
    if list == []:
RuntimeError: maximum recursion depth exceeded in cmp

完整的追溯作为一个牧场.

我已经测试了quicksort功能,它适用于普通列表(例如:list = ['Alice','Bob,'Carl','Derp']),但如果我尝试排序'名字',它就不起作用

这是我的代码

def quicksort(list):
    """Quicksort using list comprehensions"""
    if list == []:
        return []
    else:
        pivot = list[0]
        lesser = quicksort([x for x in list[1:] if lessThan(x, pivot)])
        greater = quicksort([x for x in list[1:] if not lessThan(x, pivot)])
        return lesser + [pivot] + greater

def lessThan(a, b):
    return len(a) < len(b)

#'''
input = open('Names.txt', 'r')
output = open('Names Arranged By Length.txt', 'w')

names = []

for line in input:
    line = line.translate(None, '\n')
    names.append(line)


names = quicksort(names)

for i in names:
    print i
    output.write(i)
    output.write('\n')

print 'Count: ', len(names)


input.close()
output.close()
#'''

我的代码有什么问题,我该如何解决？

Answer 1

你只需要达到递归限制.您的名称列表对于Python的有限递归功能来说太大了.你的Quicksort工作正常.

您可以通过将限制设置为更高来提高递归限制sys.setrecursionlimit().您可以将其设置得更高,但您需要自担风险.

更好的选择是使用内置的Python排序; 该TimSort算法远远优于并不会打一个递归限制:

names = sorted(names, key=len)

这会根据长度,最短的名称对名称进行排序.

Answer 2

您超过了python默认的递归大小。默认递归限制为1000。您可以增加递归限制，但不建议这样做。这是怎么做的

import sys
sys.setrecursionlimit(1500)

建议
我的建议是使用numpy.argsort（）方法，该方法已经为许多排序算法准备好了。这是有关如何使用numpy库执行quicksort算法的简单示例。