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

Question

我正在写一个程序，这个程序会读取一个包含5163个名字的文本文件。（你可以在这里查看这个文本文件）

然后我想把这些名字存储到一个叫做'names'的列表里，接着我会根据名字的字母数量对这个列表进行排序，短的名字排在前面，长的名字排在后面。

我使用了快速排序来对列表进行排序，但当我运行程序时，出现了这个错误：

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

完整的错误信息可以在这里查看。

我测试过快速排序的函数，它在普通的列表上（比如：list = ['Alice','Bob','Carl','Derp']）是可以正常工作的，但如果我尝试对'names'进行排序，就不行了。

这是我的代码：

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默认的递归大小限制。默认的递归限制是1000。虽然你可以增加这个限制，但不推荐这样做。下面是如何操作的

import sys
sys.setrecursionlimit(1500)

建议
我建议使用 numpy.argsort() 方法，因为它已经为多种排序算法做好了准备。这里有一个简单的例子，展示了如何使用numpy库来实现快速排序算法。

Answer 2

你遇到的问题是递归限制。你的名字列表太大了，超出了Python的递归能力。其实你的快速排序算法本身是没问题的。

你可以通过使用sys.setrecursionlimit()来提高递归限制。你可以把这个限制调得高一些，但这样做有风险。

更好的选择是使用Python自带的排序功能；TimSort算法要好得多，而且不会遇到递归限制：

names = sorted(names, key=len)

这个排序是按照名字的长度来排序的，从短到长。