Python,递归,排序和堆栈溢出

Question

今天在课堂上,我让我的学生在Python 3.2中编写了一个递归的快速排序(从教科书中复制).我以相反的顺序给了他们10,000个整数的文本文件(以说明更糟糕的情况).当学生创建要排序的字符串列表时,他们的代码正常工作.如果学生使用整数列表(从文本文件输入转换),则他们的代码崩溃,最大递归深度超出错误.关于为什么使用整数列表的任何想法都会导致这些结果？

仅供参考 - 我可以将学生的代码从int更改为字符串列表,反之亦然,并始终重新创建问题.

Answer 1

让我猜一下:文件看起来像

10000
9999
9998

这些字符串的排序顺序是词典,因此不同于它们所代表的整数:

>>> sorted(x)
['10000', '9998', '9999']
>>> sorted(x, key=int)
['9998', '9999', '10000']

根据int顺序,数组因此被反向排序,给出了快速排序的最坏情况性能.但是在字典顺序中,它与反向排序相差甚远; 我刚刚编写的完全天真的快速排序在输入上达到的最大递归深度仅为130 map(str, range(1, 10001)).显然,如果range(1, 10001)没有Sedgewick的尾递归优化,它确实会爆炸,因为所需的递归深度恰好是10000.