排序不等式

排序不等式是數學上的一條不等式。它可以推導出很多有名的不等式，例如算術幾何平均不等式（簡稱算幾不等式），柯西不等式，和切比雪夫總和不等式。它是說：

如果 x_1 \le x_2 \le \cdots \le x_n，和 y_1 \le y_2 \le \cdots \le y_n 是兩組實數。而 x_{\sigma(1)}, \ldots, x_{\sigma(n)} 是x_1, \ldots , x_n的一個排列。排序不等式指出 x_1y_1 + \cdots + x_ny_n \ge x_{\sigma (1)}y_1 + \cdots + x_{\sigma (n)}y_n \ge x_ny_1 + \cdots + x_1y_n。

以文字可以說成是順序和不小於亂序和，亂序和不小於逆序和。與很多不等式不同，排序不等式不需限定x_i, \, y_i的正負。

證明
排序不等式可以用數學歸納法證明。關鍵在於下列結果：

若 x_i \le x_j, \, y_i \le y_j，則有 (x_j - x_i)(y_j - y_i) \ge 0

移項得出 x_i y_i + x_j y_j \ge x_j y_i + x_i y_j。

重複以上步骤便可得出排序不等式。

我们设 S_i 为 b_1,b_2, \dots b_n 原序列的前 i 个数的和，即 S_i=b_1+b_2+\dots b_i。

设 S' 为打乱顺序后的序列，S'_i 表示乱序后的前 i 个数的和。所以有 S_i \le S'_i。

注意到 a_n-a_{n+1} \le 0，则 S_i \times (a_n-a_{n+1}) \ge S'_i \times (a_n-a_{n+1})

\sum_{k=1}^n a_k b_k = \sum_{k=1}^{n-1} S_k(a_k-a_{k+1})+S_na_n \ge \sum_{k=1}^{n-1} S'_k(a_k-a_{k+1})+S'_na_n(S'_n=S_n)

得证。