Python 快速排序运行时错误：cmp 中超出最大递归深度

我正在编写一个程序，它将读取包含 5,163 个姓名的文本文件。 （文本文件可见here http://pastebin.com/BAKTJKy6)

然后我想将名称存储到一个名为“名称”的列表中，之后，我根据名称包含的字母数量对列表进行排序，较短的名称位于列表的开头，较长的名称位于列表的末尾。

我使用快速排序对列表进行排序，但是当我运行它时，它显示以下错误：

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

完整的追溯可用作为馅饼 http://pastebin.com/cC671BTd.

我已经测试了快速排序函数，它适用于普通列表（例如：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()
#'''

我的代码有什么问题以及如何修复它？

您只是达到了递归限制。对于 Python 有限的递归功能来说，您的名称列表太大了。否则你的快速排序就可以正常工作。

You could通过将限制设置得更高来提高递归限制sys.setrecursionlimit() https://docs.python.org/2/library/sys.html#sys.setrecursionlimit。您可以将其设置得较高，但您需要自行承担风险。

更好的选择是使用内置的 Python 排序；这TimSort算法 http://en.wikipedia.org/wiki/Timsort优越得多并且不会达到递归限制：

names = sorted(names, key=len)

这将按名称的长度对名称进行排序，首先是最短的名称。