两种排序的最坏比较次数
把五个元素的全部 120 种排列都跑一遍，插入排序和归并排序各自最坏比了多少次： import math from itertools import permutations def merge_c
阅读更多 →
五个元素的下界是多少
五个元素一共有多少种排列？装下这么多叶子的二叉树至少多高？ import math from itertools import permutations def merge_cmp(a):
阅读更多 →
这个下界管的是哪一种情况
比较排序的这个下界，说的是【0】。
阅读更多 →
⚠️ 决策树的叶子对应什么
把一个比较排序画成决策树，每个叶子对应【0】。
阅读更多 →
「下界」说的是什么
说比较排序有一个下界，意思是【0】。
阅读更多 →
交付：基线 / 归纳步 / 不丢元素
把归纳证明的三件事各写成一次检查。归纳步拿 [1,4,6] 和 [2,3,5] 两个已经排好的半边去合并；"不丢元素"拿 [0,1,2,4,3] 验。
阅读更多 →
🔴 120 种输入里，错的那版有几种照样对
把五个元素的全部 120 种排列都喂给 msort_bad，数一数有多少种它照样给出了正确结果。
阅读更多 →
自己写：把合并的最后一步补上
补全归并的收尾——循环出来时，两边一定有一边还剩着。
阅读更多 →
⚠️ 换一个输入，它就露馅了
同一个 msort_bad，换成 [0, 1, 2, 4, 3]： def msort(a): if len(a) <= 1: return list(a) m
阅读更多 →
错的那版，在已排好序的输入上给什么
下面 msort_bad 漏了合并的最后一句。先拿最顺手的那个测试用例——已经排好序的数组——试试： def msort(a): if len(a) <= 1: retu
阅读更多 →