解： 13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11 9, 19, 13, 5, 12, 8, 7, 4, 21, 2, 6, 11 9, 5, 13, 19, 12, 8, 7, 4, 21, 2, 6, 11 9, 5, 8, 19, 12, 13, 7, 4, 21, 2, 6, 11 9, 5, 8, 7, 12, 13, 19, 4, 21, 2, 6, 11 9, 5, 8, 7, 4, 13, 19, 12, 21, 2, 6, 11 9, 5, 8, 7, 4, 2, 19, 12, 21, 13, 6, 11 9, 5, 8, 7, 4, 2, 6, 12, 21, 13, 19, 11 9, 5, 8, 7, 4, 2, 6, 11, 21, 13, 19, 12 return 8

解：r；可以检查所有元素的值都相同的情况

易证。

解：第四行的≤改为≥。

证明： T ( n ) ≥ c 1 ( n − 1 ) 2 + c n = c 1 n 2 − 2 c 1 n + c 1 + c n ≥ c 1 n 2 T(n)\geq c_1(n-1)^2+cn=c_1n^2 - 2c_1n+c_1+cn\geq c_1n^2 T(n)≥c1​(n−1)2+cn=c1​n2−2c1​n+c1​+cn≥c1​n2 ( c − 2 c 1 ) n + c 1 ≥ 0 (c-2c_1)n+c_1\geq 0 (c−2c1​)n+c1​≥0 c 1 ≤ c 2 c_1 ≤ \frac{c}{2} c1​≤2c​ T ( n ) ≤ c 2 ( n − 1 ) 2 + c n = c 2 n 2 − 2 c 2 n + c 2 + c n ≤ c 2 n 2 T(n) ≤ c_2(n-1)^2 + cn = c_2n^2 - 2c_2n + c_2 + cn ≤ c_2n^2 T(n)≤c2​(n−1)2+cn=c2​n2−2c2​n+c2​+cn≤c2​n2 ( c − 2 c 2 ) n + c 2 ≤ 0 (c - 2c_2)n + c_2\leq 0 (c−2c2​)n+c2​≤0 c 2 ≥ c 2 c_2 ≥ \frac{c}{2} c2​≥2c​ ……

解： Θ ( n 2 ) Θ(n^2) Θ(n2)

证明（翻译自参考答案）：所有元素降序排列时我们运行的是“最坏情况PARTITION”。它每一步只将要考虑的子数组大小减1，运行时间 Θ ( n 2 ) Θ(n^2) Θ(n2)。

本题证明翻译自https://ita.skanev.com/07/02/04.html 证明： 一个简单直观的论证就足够了。 数组排序越多，插入排序的工作量就越少。即，INSERTION-SORT是Θ(n+d)，其中d是阵列中的逆序对个数。 在上面的例子中，逆序对往往很少，因此插入排序将接近线性。 另一方面，如果PARTITION确实选择了不在逆序对中的元素，它将产生一个空分区。由于存在逆序对很少，QUICKSORT很可能产生空分区。

证明： （1）最小深度： αmn=1 m=-logαn=-lgn/lgα （2）最大深度： （1-α)Mn=1 M=-lgn/lg(1-α)

证明： 设 n l n_l nl​和n r _r r​代表左右两边的比例，更均衡表示 ∣ n l − n r ∣ ; 1 − 2 α |n_l-n_r| ; 1-2α ∣nl​−nr​∣