排序不等式

排序不等式是数学上的一条不等式。它可以推导出很多有名的不等式，例如算术几何平均不等式(简称算几不等式)，柯西不等式，和切比雪夫总和不等式。它是说：

如果

是两组实数。而

是${\displaystyle x_1,\dots <!--\; \dots \; -->,x_n}$的一个排列。排序不等式指出

以文字可以说成是顺序和不小于乱序和，乱序和不小于逆序和。与很多不等式不同，排序不等式不需限定${\displaystyle x_i,y_i}$的符号。

排序不等式可以用数学归纳法证明。关键在于下列结果：

若${\displaystyle x_i\le <!--\; \le \; -->x_j,y_i\le <!--\; \le \; -->y_j}$，则有

移项得出

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

我们设Si为b1,b2,...bn 原序列 的前i个数的和，即Si=b1+b2+...bi；设S' 为打乱顺序后的序列，S'i表示乱序后的前i个数的和。所以有：Si<=S'i. 注意到 a-a<=0 则 Si*(a-a)>=S'i*(a-a)

${\displaystyle \underset{k=1}{\overset{N}{\sum <!--\; \sum \; -->}}a\ast <!--\; \ast \; -->b=\underset{k=1}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}Sk\ast <!--\; \ast \; -->(a-<!--\; -\; -->a)+Sn\ast <!--\; \ast \; -->an>=\underset{k=1}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{S}^{\prime }k\ast <!--\; \ast \; -->(a-<!--\; -\; -->a)+S^{\prime }n\ast <!--\; \ast \; -->an(S^{\prime }n=Sn)}$得证