Unfortunately, Program 2 is sometimes much slower.
On arrays that are already sorted, it makes roughly n 2 /2 comparisons. To avoid this problem Hoare suggests partitioning around a random element; we adopt the technique in Program 3. Program 2 also takes quadratic time on arrays of identical elements.
经典考点: quicksort 何时退化. 已排好序 / 全相等(可看作全排好序)
如何找 flag:
直接找 a[0] 很粗暴. 如果直接找 medium 耗时, 所以从 a[0] a[-1] a[med] 里面选中间的.
但是这样对小数组不友好, 所以根据 size 切换策略.
Dutch national flag problem
1. 利用 radix sort, 用 [color; 3] 存数量
- impl Ord for color 然后 sort
Hoare_logic
Hoare_logic 可以看成一个状态转移.
P → Q
P 为真, 经过 body, 转移成 Q
Simplicity. The key to performance is elegance, not battalions of special cases. The terri-
ble temptation to tweak should be resisted unless the payoff is really noticeable.
Profiling Tools. A function-time profiler tells us where the CPU cycles go, and a line-
count profiler tells us why. A cost model gives us ballpark estimates for key operations.
We sometimes used an algorithm animation system to make movies of sort functions.
Testbeds for Timing and Debugging. A tiny driver gives us one glimpse of the program; a
more complex testbed exercises it in more interesting ways. The testbeds check correctness,
count comparisons and measure CPU times.
Testing and Certification. The correctness and performance of key routines should be val-
idated by certification programs.
