排序算法之：最小平均等待时间调度（Shortest Average Wait Time Scheduling）的贪心策略证明与算法实现
题目描述
假设有 \(n\) 个任务，每个任务有一个处理时间 \(t_i\)。任务按照某种顺序依次处理（单线程），每个任务从开始处理到完成的时间称为完成时间。每个任务的等待时间定义为它的完成时间减去它的处理时间（即从任务到达至开始处理的时间）。
目标：安排任务的顺序，使得所有任务的平均等待时间最小。
输入：一个数组 times，表示每个任务的处理时间。
输出：最小平均等待时间（或等价地，最小总等待时间）。
解题过程
步骤1：理解等待时间的计算
设任务的处理顺序为 \(p_1, p_2, \dots, p_n\)，对应处理时间为 \(t_{p_1}, t_{p_2}, \dots, t_{p_n}\)。
- 第一个任务 \(p_1\) 的完成时间 = \(t_{p_1}\)，等待时间 = 0。
- 第二个任务 \(p_2\) 的完成时间 = \(t_{p_1} + t_{p_2}\)，等待时间 = \(t_{p_1}\)。
- 第三个任务 \(p_3\) 的完成时间 = \(t_{p_1} + t_{p_2} + t_{p_3}\)，等待时间 = \(t_{p_1} + t_{p_2}\)。
- ...
- 第 \(k\) 个任务 \(p_k\) 的等待时间 = \(\sum_{j=1}^{k-1} t_{p_j}\)。
总等待时间 =
\[\sum_{k=1}^n \left( \sum_{j=1}^{k-1} t_{p_j} \right) \]
步骤2：将总等待时间写成更直观的形式
交换求和顺序：
总等待时间 =
\[\sum_{j=1}^n t_{p_j} \cdot (n - j) \]
这里 \(j\) 是任务在顺序中的位置（从1开始），\((n-j)\) 表示这个任务之后有多少个任务（包括自己？不，不包括自己）。
更准确地说，任务在位置 \(j\) 时，它之后有 \(n-j\) 个任务，这 \(n-j\) 个任务在等待它完成，所以它的处理时间会贡献给后面 \(n-j\) 个任务的等待时间。
因此：
总等待时间 = \(t_{p_1} \cdot (n-1) + t_{p_2} \cdot (n-2) + \dots + t_{p_{n-1}} \cdot 1 + t_{p_n} \cdot 0\)。
步骤3：贪心策略的猜想
由于系数从 \((n-1)\) 递减到 0，要最小化总和，应该将最小的 \(t_i\) 放在系数最大的位置（即最前面），将最大的 \(t_i\) 放在系数最小的位置（即最后面）。
所以最优策略是：按照处理时间从小到大排序（最短作业优先，Shortest Job First, SJF）。
步骤4：证明贪心策略的最优性
用交换相邻项的方法证明：
假设在最优顺序中，存在相邻的两个任务 \(A\) 和 \(B\)，其中 \(t_A > t_B\)，且 \(A\) 在 \(B\) 前面。
设它们前面的任务总时间为 \(P\)，后面的任务数为 \(m\)（这两个任务不在其内）。
当前顺序 \(\dots, A, B, \dots\) 中，\(A\) 和 \(B\) 对总等待时间的贡献（只考虑它们两个任务带来的等待时间增加）为：
- \(A\) 的贡献：\(t_A \cdot (m+1)\)（因为 \(B\) 和后面 \(m\) 个任务要等 \(A\) 完成）
- \(B\) 的贡献：\(t_B \cdot m\)
交换 \(A\) 和 \(B\) 得到顺序 \(\dots, B, A, \dots\)：
- \(B\) 的贡献：\(t_B \cdot (m+1)\)
- \(A\) 的贡献：\(t_A \cdot m\)
交换前后的贡献差：
\[[t_A(m+1) + t_B m] - [t_B(m+1) + t_A m] = t_A - t_B \]
由于 \(t_A > t_B\)，差值 \(> 0\)，说明交换后总等待时间更小，与最优矛盾。
因此最优顺序中任意相邻两项必满足 \(t_{\text{前}} \le t_{\text{后}}\)，即非递减顺序。
步骤5：算法实现
只需对 times 数组排序，然后计算总等待时间。
计算总等待时间的高效方法：
排序后 times[0] 是第一个任务，它贡献的等待时间为 0，但它会让后面的任务等它。
从公式 \(\sum_{j=1}^n t_j \cdot (n-j)\) 出发，可以直接计算：
def min_total_wait_time(times):
times.sort() # 升序排列
total_wait = 0
n = len(times)
for i in range(n):
total_wait += times[i] * (n - i - 1) # 第 i 个任务（0-index）影响后面 n-i-1 个任务
return total_wait
平均等待时间 = total_wait / n。
步骤6：举例验证
输入：times = [5, 2, 1, 3]
排序后：[1, 2, 3, 5]
计算：
- 1 贡献：1 * 3 = 3
- 2 贡献：2 * 2 = 4
- 3 贡献：3 * 1 = 3
- 5 贡献：5 * 0 = 0
总等待时间 = 10
平均等待时间 = 10 / 4 = 2.5
可以手工验证顺序 [1,2,3,5] 的等待时间：
任务1 等待=0，任务2 等待=1，任务3 等待=1+2=3，任务4 等待=1+2+3=6，总=0+1+3+6=10 ✅
步骤7：扩展思考
- 如果任务有不同的到达时间，问题变为“最短剩余时间优先”调度，更复杂。
- 本题的贪心证明也适用于最小化总完成时间（因为总完成时间 = 总等待时间 + 总处理时间，总处理时间是常数）。
- 在现实中，SJF 可减少平均等待时间，但可能导致长任务饥饿。
总结：
最短作业优先（SJF）是使平均等待时间最小的最优策略，证明基于交换相邻逆序对会减少总等待时间的思路。实现只需排序并加权求和，时间复杂度 \(O(n \log n)\)。