排序不等式（也称为重排不等式或Chebyshev不等式）是数学中的一个重要不等式，它描述了两组实数在特定排序下的乘积和的最小值和最大值。以下是对排序不等式的证明过程：
排序不等式的形式
假设有两个序列 $a_1, a_2, \ldots, a_n$ 和 $b_1, b_2, \ldots, b_n$，且它们都是非降序排列的（即 $a_1 \leq a_2 \leq \cdots \leq a_n$ 且 $b_1 \leq b_2 \leq \cdots \leq b_n$）。则有以下两个不等式成立：
反向排序和最小：若将 $b_i$ 按相反顺序重新排列为 $b'i = b{n+1-i}$，则有 [ \sum_{i=1}^{n} a_i b'i \leq \sum{i=1}^{n} a_i b_{\sigma(i)} \leq \sum_{i=1}^{n} a_i b_i ] 其中 $\sigma$ 是任意置换。
同向排序和最大：直接按照原顺序相乘时，和达到最大，即 [ \sum_{i=1}^{n} a_i b_i \geq \sum_{i=1}^{n} a_i b_{\sigma(i)} ] 对于所有其他排列都成立。
证明思路
反向排序和最小的证明
考虑两个相邻元素 $a_k$ 和 $a_{k+1}$ 以及对应的 $b'{k}$ 和 $b'{k+1}$（注意 $b'$ 是 $b$ 的逆序），不失一般性，我们假设 $a_k \leq a_{k+1}$ 和 $b'k \geq b'{k+1}$。
交换 $a_k b'{k}$ 和 $a{k+1} b'{k+1}$ 对总和的影响是： [ \Delta = (a{k+1} b'k + a_k b'{k+1}) - (a_k b'k + a{k+1} b'{k+1}) = (a{k+1} - a_k)(b'k - b'{k+1}) ] 由于 $a_{k+1} - a_k \geq 0$ 且 $b'k - b'{k+1} \leq 0$，所以 $\Delta \leq 0$。这表明通过交换可以使总和变小或保持不变。因此，经过一系列这样的交换，我们可以得到按 $a$ 升序、$b'$ 降序排列时的和是最小的。
同向排序和最大的证明
同理，对于同向排序的情况，如果 $a_k \leq a_{k+1}$ 且 $b_k \leq b_{k+1}$，则 [ \Delta = (a_{k+1} b_{k+1} + a_k b_k) - (a_k b_{k+1} + a_{k+1} b_k) = (a_{k+1} - a_k)(b_{k+1} - b_k) ] 此时 $\Delta \geq 0$，因为 $a_{k+1} - a_k \geq 0$ 且 $b_{k+1} - b_k \geq 0$。这表明保持 $a$ 和 $b$ 的升序排列可以得到和的最大值。
结论
通过上述分析，我们证明了排序不等式的正确性。这个不等式在数学竞赛、信息论和其他领域都有广泛的应用。
