这是一个创建于 1686 天前的主题，其中的信息可能已经有所发展或是发生改变。
迫于最近不小心看到了《算法图解》，遂开始学习排序；当试到快排时，有个问题让人很疑惑:
最初版本：
这里当递归出口条件为 数组长度等于 1 时，会报错；
修改后的版本：
将出口条件修改为数组长度<2 时，就能正常运行
问题： len(array)<2 和 len(array) == 1 这两句话不是等价的么？？？？？
 |
1
chairuosen 2020-05-15 11:09:46 +08:00
也可能是 0 啊
|
 |
2
shintendo 2020-05-15 11:11:16 +08:00
等于 1 和小于 2 怎么会是等价的？？
|
 |
3
craiiz OP |
 |
4
gwy15 2020-05-15 11:16:54 +08:00
怎么就到不了 0 了，
qs([1,0]) -> pivot=1, greater = [], smaller = [0] qs([]) -> boom |
|
5
craiiz OP @shintendo 我是这么想的：列表长度不可能小于 0 吧？ 可能是 0，但要变为 0，肯定会先变成 1 。既然两种情况(被排序的列表不停地被拆分)都必然会经过 len(array) == 1 的情况，那么在这限定条件下，这两种写法就是等价的。
|
 |
6
rabbbit 2020-05-15 11:17:53 +08:00
例如 1 2 3 4 5 6
此时 base_line 为 1 greaters 为 [2, 3, 4, 5, 6] smallers 为 [] 所以报错了 |
|
9
craiiz OP 此题终结
|
|
10
chairuosen 2020-05-15 11:19:15 +08:00
另外：遇到自己想不明白的问题，每一行结果都打日志看呀，又不是黑盒
|
 |
11
yuruizhe 2020-05-15 11:20:32 +08:00
@craiiz 当 pivot 是最小值，smallers 是一个空数组，继续对 smallers 调用 sort()，就会无限递归下去；反之，当 pivot 是最大值，greaters 是一个空数组，继续对 greater 调用 sort()，也会无限递归下去，用例：[1,6,5,4,3,2,]
|
|
12
craiiz OP @chairuosen 了解，我用 IDE 好了，现在想着学习就只用终端加记事本了。
|
 |
14
crella 2020-05-15 11:31:25 +08:00
我看其他人写的 py 脚本，一般不都是把 import 语句放在文件开头的吗？
|
Select Language