通过交换操作,调整数组元素位置

时间:2022-12-03 19:04:49

问题描述:有一个长度为N的整形数组row,由0至N-1这N个数字乱序组成(每个数组出现且仅出现一次)。现在你可以对这个数组的任意两个不同的元素进行交换。问:对于一个给定的这种数组,若要把这个数组变为从小到大排好序的操作(即,对于数组的任意下标,均有 I == row[i] 成立),最少需要进行多少次交换?

 

首先,举几个简单的例子:

 

例子1:

 

下标

0

1

2

3

4

0

3

2

1

4

 

只需1次交换即可:把row中下标为1的元素和下标为3的元素进行交换,记为swap(row, 1, 3)。

 

 

例子2:

下标

0

1

2

3

4

0

2

1

4

3

 

需要两次交换:

第一次:swap(row, 1, 2)

第一次交换后:

下标

0

1

2

3

4

0

1

2

4

3

 

第二次:swap(row, 3, 4)

 

 

例子3:

下标

0

1

2

3

4

0

4

2

1

3

 

需要两次交换:

第一次:swap(row, 1, 4)

第一次交换后:

下标

0

1

2

3

4

0

3

2

1

4

 

第二次:swap(row, 1, 3)

 

 

注意,在例子3中,下标为1、3、4的三个元素的初始位置形成了一个“环”。即(接下来的话很重要),位置1上的元素本应该在位置4;位置4上的元素本应该在位置3;位置3上的元素本应该在位置1。这段很重要的话太啰嗦了,简记如下:1-->4-->3-->1。

 

任何一个乱序的数组,都会包含一个或多个形如“1-->4-->3-->1”的“环”。

 

注意,这个“环”的开头的结尾肯定是同一个下标,绝不会出现如下的形式:

“1-->4-->3-->……-->3”。这是因为,如果数字3出现了两次,那就意味着原始数组row中的两个不同的位置的元素都“本应该出现在位置3”。

 

所以,“通过交换的方式对数组进行排序”,其实就是“对上述的‘环’中的下标进行操作”。

 

下面来计算对每个“环”需要进行多少次交换。

 

首先定义“环”的长度如下:

“1-->4-->3-->1”的长度为3,

“1-->4-->1”的长度为2

“1-->1”的长度为1(长度为1的情况就是“该元素的处于正确位置”的情况)

 

对于长度为1的环,所需的交换次数是0,SWAP(1) = 0

对于长度为2的环,所需的交换次数是1,SWAP(2) = 1

对于长度为k的环,交换其中的任何两个元素,把当前的“撕裂”为两个更小的环,且两个小环的长度加起来刚好等于k。例如:

对于环:

……i-->j-->k-->……r-->s-->t-->……

执行swap(row, j, s),会生成如下的两个环(需要思考两分钟):

环1:……i-->j-->t-->……

环2:k-->……r-->s->k

(对于j和s在边界的情况,上述结论也成立。)

为什么环1中,j的后面是t,也就是说,为什么位置j的元素本应位于位置t?

因为,在执行了swap(row, j, s)之后,原来位置s的元素就跑到了位置j上。交换前,“s-->t”表示“位置s的元素本应位于位置t”,所以,在位置s的元素跑到位置j后,就成了“位置j的元素本应位于位置t”。同样的道理可以解释为什么环2中s的后面是k。

 

所以,对于长度为k的环,所需的交换次数SWAP(k)=SWAP(k1) + SWAP(k2) +1,其中k1+k2=k

 

 

根据

SWAP(1) = 0,

SWAP(k)=SWAP(k1) + SWAP(k2) +1,其中k1+k2=k

可以用第二数学归纳法证明(第二数学归纳法是啥,见文末),

SWAP(n) = n - 1

 

注意,对长度为k的环,交换其中的任意两个元素都可以把环撕裂为两个小环。那么,如果我们把第一个元素交换到“它本应出现的位置”,会怎样呢?

对于环“1-->4-->3-->1”,下标1上的元素本应出现在位置4,所以我们执行swap(row, 1, 4),然后就把“1-->4-->3-->1”撕裂为两个小环:

环1:“1-->3-->1”

环2:“4-->4”

 

环2是“已经搞定了”的状态,接下来只需处理环1,swap(row, 1, 3)。

 

上述算法的直观感觉就是,不停地把“当前位置的元素”和“它应该去的地方”的元素进行交换,这样,“当前位置的元素”就去了“它应该去的地方”,同时,“被换过来的元素”又成了“当前位置的元素”,直到“被换过来的元素”就应该放在“当前位置”为止。

 

代码如下:

int sort(int[] row) {

        printArray(row);

       

        int nSwapTimes = 0;

        for (int i = 0; i < row.length; ++i) {

                 for (int j = row[i]; j != i; j = row[i]) {

                         swap(row, i, j);

                         ++ nSwapTimes;

       

                         // 可以在每次交换后把row的当前状态打印出来感受一下

                         printArray(row);

                 }

        }

        return nSwapTimes;

}

 

上述解法可以推广到如下的问题:

有N对夫妇随机坐成一排,现在要经过若干次交换座椅,使得每对夫妇的座位都挨在一起。求最小的交换次数。座位以整形数组row表示,下标从0至2N-1。每一对夫妇都用有序数对表示:(0, 1)、(2, 3)、(2N-2, 2N-1)。数组row的第i个元素row[i]代表位置i上坐着的人。

 

为了解决这个问题,需要一个和row的用处刚好相反的辅助数组pos:row[i]代表位置i上坐着的人;pos[i]代表人i所在的位置。

 

为了方便起见,定义getPartner函数如下

int getPartner(int n) {

        return (n % 2 == 1) ? (n - 1) : (n + 1);

}

这个函数返回下标n的配偶(n既可以是人也可以是座位。请思考两分钟,当n是座位时getPartner的含义)。

 

这个问题和乱序数组的排序问题只有一个区别:

乱序数组排序:下标i所在的元素的期望位置是row[i]

本问题:下标i所在元素的期望位置是getPartner(pos[getPartner(row[i])])

getPartner(pos[getPartner(row[i])])的含义:

最内层row[i],位置i上的人是谁

再加一层getPartner,此人的配偶是谁

再加一层pos,此人的配偶在row中的实际座位

再加一层getPartner,此人的期望座位(思考两分钟)

 

代码如下:

int nResult = 0;

for (int i = 0; i < row.length; i += 2) {

        for (int j = getPartner(pos[getPartner(row[i])]); j != i; j = getPartner(pos[getPartner(row[i])])) {

                 swap(row, i, j);

                 swap(pos, row[i], row[j]);

                 ++nResult;

        }

}

 

return nResult;

 

 

至此,结束

 

第一数学归纳法,若对自然数的命题P(n),满足:

1、  P(1)成立。

2、  若P(k)成立,则P(k+1)成立

则P(n)对全体自然数成立。

 

 

第二数学归纳法,若对自然数的命题P(n),满足:

1、  P(1)成立。

2、  若P(1),P(2),……,P(k)成立,则P(k+1)成立

则P(n)对全体自然数成立。