排序算法的传递性

---

如果有{甲, 乙, 丙} 三个对象, 规定:
甲>乙
乙>丙
丙>甲
则: 这种排序没有传递性

排序算法的传递性证明

如果
$\Large a.b <= b.a$, 则$\Large a$放在前面, 否则 $\Large b$放在前面

则, 根据排序算法的传递性:
数组中的元素根据字典序排序以后:
[…前…后…]
任何两个元素结合, 则应该有:
前.后 <= 后.前

证明

已知:
$\Large \begin{cases} a.b <= b.a \\ b.c <= c.b \end{cases}$

求证:
$\Large a.c <= c.a$

字符串"ks" 拼接 字符串 “te” 组成新串 “kste”, 我们认为字符串就是K进制的正数, "kste"是一个四位数, "ks"占据高位, "te"占据低位, 则:
$\Large kste = ks * 26^2 + te$

认为是k进制数:
$\Large a* b = a * k^{b的长度} + b$

定义:
$\Large k^{x长度} = m(x)$, 则:

$\Large \begin{cases} a.b <= b.a \Rightarrow a*m(b) + b <= b* m(a) + a & ① \\ b.c <= c.b \Rightarrow b*m(c) + c <= c* m(b) + b & ② \end{cases}$

①两边同时 $\Large-b$ 再 $\Large*c$则有:

$\Large a* m(b)* c <= b* m(a) *c + a*c -bc$

②两边同时 $\Large-b$ 再 $\Large*a$则有:

$\Large b* m(c)* a + c*a - b*a<= c* m(b) *a$

由上面两式, 可以得到:
$\Large b* m(a) *c + a*c -b*c >= b* m(c)* a + c*a - b*a$

$\Large \Rightarrow$

$\Large b* m(a) *c -b*c >= b * m(c)* a - b*a$

$\Large \Rightarrow$

$\Large m(a) *c -c >= m(c)* a - a$

$\Large \Rightarrow$

$\Large a.c <= c.a$

任何一个在前的跟一个在后的交换不会得到更大的字典序

$\Large [... a ... b...]$

假设$\Large a,b$中有两个字符串, $\Large m_1, m_2$, 即:

$\Large [... a m_1 m_2 b...]$,则任何一个在前的$\Large a$,跟在后的$\Large b$交换顺序, 拼起来的新的字符串的字典序一定比之前要大

$\Large [... b m_1 m_2 a...]$

证明

原序列中顺序为$\Large am_1 m_2 b$, 我们把$\Large a$跟$\Large m_1$交换顺序得到:

$\Large [... m_1 a m_2 b...]$

即: $\Large a.m_1 <= m_1.a$, 后面没有改变,则有:

$\Large [... m_1 a m_2 b...] >= [... a m_1 m_2 b...]$
我们继续交换$\Large a$跟$\Large m_2$,

即: $\Large a.m_2 <= m_2.a$
则有:

$\Large [... m_1 m_2 a b...] >= [... m_1 a m_2 b...]$
我们继续交换$\Large a$跟$\Large b$,
则有:

$\Large [... m_1 m_2 b a...] >= [... m_1 m_2 a b...]$

将b跟$\Large m_2, m_1$依次交换, 由上相同可得:

$\Large [... b m_1 m_2 a...] >= [... a m_1 m_2 b...]$