排序算法-最少交换次数证明
排序算法-最少交换次数证明,本文没有使用群等“高深概念”。对于排序的最少交换次数的计算公式进行了简单的证明。记录一下以便查阅。
最少交换次数证明
1. 问题介绍
问题:对第一行数据进行排序,可以任意交换两个元素,求最少的交换次数是多少?
结论:
F
(
N
)
=
N
n
o
d
e
−
N
r
i
n
g
F(N)=N_{node}-N_{ring}
F(N)=Nnode−Nring
其中,
F
(
N
)
F(N)
F(N)为最少交换次数,
N
n
o
d
e
N_{node}
Nnode为数组长度(或节点数),
N
r
i
n
g
N_{ring}
Nring为交换环(或称可交换环)的个数。
交换环:对于元素 a i j a_{ij} aij,其中 i i i 表示该元素排序前的下标, j j j 表示排序后的下标,若存在一个 n ( n > 0 ) n(n>0) n(n>0) 个元素序列 { a i j } \{a_{ij}\} {aij},满足:1. j n = i 1 j_n=i_1 jn=i1;2. j k = i k + 1 ( 1 ≤ k < n ) j_k=i_{k+1}(1\le k < n) jk=ik+1(1≤k<n),则称序列 { a i j } \{a_{ij}\} {aij} 为交换环。
2. 案例
对于数列
{
32
,
74
,
25
,
53
,
28
,
43
,
86
,
47
}
\{32, 74, 25, 53, 28, 43, 86, 47\}
{32,74,25,53,28,43,86,47} 可以对任意 2 个元素进行交换操作,则使得该序列由小到大排列,至少需要多少次交换?
说明:第一行是排序前数据的序列,第二行是排序后数据的序列。
对于案例中 { 3 2 ( 0 , 2 ) , 2 5 ( 2 , 0 ) } \{32_{(0,2)},25_{(2, 0)}\} {32(0,2),25(2,0)} 是一个交换环, { 2 8 ( 4 , 1 ) , 7 4 ( 1 , 6 ) , 8 6 ( 6 , 7 ) , 4 7 ( 7 , 4 ) } \{28_{(4,1)},74_{(1,6)},86_{(6,7)},47_{(7,4)}\} {28(4,1),74(1,6),86(6,7),47(7,4)} 是一个交换环, { 5 3 ( 3 , 5 ) , 4 3 ( 5 , 3 ) } \{53_{(3,5)},43_{(5,3)}\} {53(3,5),43(5,3)} 是一个交换环。
则最少交换 8 − 3 = 5 8 - 3 = 5 8−3=5 次。
3. 证明过程
注:注意交换环和数学中环的区别。
本文试图证明:对于长度为 N ≥ 1 N \ge 1 N≥1 任意数列,若该数列有 M ( 1 ≤ M ≤ N ) M(1 \le M \le N) M(1≤M≤N) 个交换环,则最小交换数 F N ( M ) = N − M F_N(M)=N-M FN(M)=N−M。
引理1:对于 N n o d e ≥ 2 N_{node} \ge 2 Nnode≥2 的交换环对任意两个不同节点进行交换后则成为两个交换环。
引理2: 对于两个交换环,在每个交换环中各取一个节点,将两个节点进行交换后, 两个交换环合并为一个交换环。
引理3: 对于有 N N N 个节点的交换环, 最少交换次数 F N ( 1 ) = N − 1 F_N(1)=N-1 FN(1)=N−1。
引理4:对于长度为 N ( N > 2 ) N(N>2) N(N>2) 的任意数列,若该数列有 M ( 1 ≤ M ≤ N ) M(1 \le M \le N) M(1≤M≤N) 个交换环,则最少交换数 F N ( M ) = N − M F_N(M)=N-M FN(M)=N−M。
3.1. 证明:引理1和引理2
引理1和引理2显然成立。
如上图所示,其中节点指向位置,进行交换时,对应位置的值发生改变。
3.2. 证明:引理3
使用数学归纳法证明引理3,
(1) N = 1 N=1 N=1 时, F 1 ( 1 ) = 0 F_1(1)=0 F1(1)=0 ; N = 2 N=2 N=2 时, F 2 ( 1 ) = 1 F_2(1)=1 F2(1)=1。
(2)假设当 N ≤ k , k ≥ 2 N \le k,k \ge 2 N≤k,k≥2 时,有 F N ( 1 ) = N − 1 F_N(1)=N-1 FN(1)=N−1 成立;当 N = k + 1 N=k+1 N=k+1 时, 首先任选交换环中的两个不同的节点交换,由引理1可知交换后,成为两个交换环。分别记两个交换环的节点个数为 N 1 , N 2 N_1, N_2 N1,N2, 因为 N 1 + N 2 = k + 1 N_1 + N_2 = k + 1 N1+N2=k+1 且 N 1 , N 2 ≥ 1 N_1, N_2 \ge 1 N1,N2≥1 ,所以 N 1 , N 2 ≤ k N_1, N_2 \le k N1,N2≤k,有假设可知对于两个交换环有 F N 1 ( 1 ) = N 1 − 1 , F N 2 ( 1 ) = N 2 − 1 F_{N_1}(1)=N_1-1, \ F_{N_2}(1)=N_2-1 FN1(1)=N1−1, FN2(1)=N2−1 成立。则 F k + 1 ( 1 ) = F N 1 ( 1 ) + F N 2 ( 1 ) + 1 = N 1 + N 2 − 1 = k F_{k+1}(1)=F_{N_1}(1)+F_{N_2}(1)+1=N_1+N_2-1=k Fk+1(1)=FN1(1)+FN2(1)+1=N1+N2−1=k。
即当 N = k + 1 N=k+1 N=k+1 时, F N ( 1 ) = N − 1 F_N(1) = N - 1 FN(1)=N−1 也成立。
根据数学归纳法原理,由于(1),(2)两步都成立, 所以对于任意的 N ≥ 1 , F N ( 1 ) = N − 1 N \ge 1, F_N(1) = N - 1 N≥1,FN(1)=N−1 都成立。
3.3. 证明:引理4
使用数学归纳法证明引理4,
(1)当 M = N M=N M=N 时,该数列中每个节点都自指成交换环,不需要进行交换操作,故 F N ( N ) = 0 = N − N F_N(N)=0=N-N FN(N)=0=N−N 成立;
(2)假设当 M ≥ m ( 1 < m ≤ N ) M \ge m(1 < m \le N) M≥m(1<m≤N) 时, F N ( M ) = N − M F_N (M) = N - M FN(M)=N−M 都成立;
那么当 M = m − 1 M = m - 1 M=m−1 时,若每次交换仅对交换环进行交换操作,不对交换环之间的节点进行交换操作,由引理3可知,至少需要进行 N − m + 1 N-m+1 N−m+1 次交换操作;
反证法证明不存在一个操作序列使得 F N ( m − 1 ) < N − m + 1 F_N (m-1) < N - m + 1 FN(m−1)<N−m+1 成立。
假设存在一种交换序列使得 F N ( m − 1 ) < N − m + 1 F_N (m-1) < N - m + 1 FN(m−1)<N−m+1 ,则该交换序列必然包含交换环间的交换操作;由引理1、引理2可知每次执行交换操作使得交换环的数量仅改变 1 1 1 ( + 1 +1 +1或 − 1 -1 −1),因为交换操作的最终状态是使得数列包含 N N N 个交换环,所以该交换序列必然存在一个已交换步数 k ≥ 1 k \ge 1 k≥1 使得交换环的个数等于 m m m,则有 F N ( m ) = N − m F_N(m)=N-m FN(m)=N−m,则 F N ( m − 1 ) = F N ( m ) + k = N − m + k ≥ N − m + 1 F_N(m-1) = F_N(m) + k = N-m+k \ge N-m+1 FN(m−1)=FN(m)+k=N−m+k≥N−m+1,与假设 F N ( m − 1 ) < N − m + 1 F_N (m-1) < N - m + 1 FN(m−1)<N−m+1 相矛盾,故假设不成立。
则不存在一个交换序列使得 F N ( m − 1 ) < N − m + 1 F_N (m-1) < N - m + 1 FN(m−1)<N−m+1 成立, 则当 M = m − 1 M = m - 1 M=m−1 时, F N ( m − 1 ) = N − m + 1 F_N (m-1) = N - m + 1 FN(m−1)=N−m+1 成立。
根据数学归纳法原理,由于(1),(2)两步都成立, 所以引理4成立。
证明结束.
4. 结论
上述证明仅供参考,如有问题欢迎讨论。
通过上述证明得出:交换方法,每次进行交换时,仅在一个可交换环中交换两个不同节点的位置,即可使得交换次数最少。
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)