作者：屎壳郎 miaosg01@163.com
日期：June 2021
版次：初版
每个排列都有相对应的唯一的反序表，根据反序表能生成唯一的排列。这两者之间有一一对应关系。那么我们如何在两者之间转换呢？即，已知排列，如何求它的反序表；反过来，知道一个反序表，如何生成相对应的排列呢？
根据反序的定义，已知排列 ( R 1 , R 2 , … , R n ) (R_1, R_2,\ldots, R_n) (R1?,R2?,…,Rn?)，其中 R k R_k Rk?的反序 b R k b_{R_k} bRk??为：位于 R k R_k Rk?之前且大于 R k R_k Rk?的数的个数。自然而然的，我们就想到了遍历统计，即 R k R_k Rk?与所有 R k R_k Rk?之前的项两两比较，统计出比 R k R_k Rk?大的数即可。但这需要 n ( n ? 1 ) 2 {n(n-1)\over2} 2n(n?1)?次比较，需要进行 n ( n ? 1 ) 4 {n(n-1)\over4} 4n(n?1)?次统计（均值，见拆分数），时间复杂度 O ( n 2 ) O(n^2) O(n2)。
那还有没有更高端大气上档次的算法呢？下面介绍一种时间复杂度为 O ( n lg ? n ) O(n\lg n) O(nlgn)算法。按二进制位进行统计，有点类似于基数排序，可参照基数排序来帮助理解。
以排列(5 9 1 8 2 6 4 7 3)为例，把它表示为二进制代码:
5
?
(
0
?
1
?
0
?
1
)
2
5\ (0\ 1\ 0\ 1)_2
5?(0?1?0?1)2?
9
?
(
1
?
0
?
0
?
1
)
2
9\ (1\ 0\ 0\ 1)_2
9?(1?0?0?1)2?
1
?
(
0
?
0
?
0
?
1
)
2
1\ (0\ 0\ 0\ 1)_2
1?(0?0?0?1)2?
8
?
(
1
?
0
?
0
?
0
)
2
8\ (1\ 0\ 0\ 0)_2
8?(1?0?0?0)2?
2
?
(
0
?
0
?
1
?
0
)
2
2\ (0\ 0\ 1\ 0)_2
2?(0?0?1?0)2?
6
?
(
0
?
1
?
1
?
0
)
2
6\ (0\ 1\ 1\ 0)_2
6?(0?1?1?0)2?
4
?
(
0
?
1
?
0
?
0
)
2
4\ (0\ 1\ 0\ 0)_2
4?(0?1?0?0)2?
7
?
(
0
?
1
?
1
?
1
)
2
7\ (0\ 1\ 1\ 1)_2
7?(0?1?1?1)2?
3
?
(
0
?
0
?
1
?
1
)
2
3\ (0\ 0\ 1\ 1)_2
3?(0?0?1?1)
