Question

第一次扫描的次数仍然为 n-1，主要差别在于第二次扫描。
第二次扫描也是 FOR 循环，每次循环内部的比较次数是 1 次，总的比较次数取决于 队列中元素的个数。假设个数为 m，那么比较次数为 m-1。
为了计算 m，我画了这样一个图。叶子结点为数组中的元素。没有标字母的节点表示其它两个孩子结点的比较结果。画出这样的图，任假设一个结点为最小元素，都能很清晰地看出其队列中元素的个数。

我们取两种最极端的情况：
假如最小元素为 A，那么其队列中的元素为 B, C, D，3 个元素
假如最小元素为 D，那么其队列中的元素为 A, B, C 中的最小值，1 个元素。
结论，方法改进一的比较次数最多为 2n-3，最少为 n-1，取决于最小元素所在位置。