数组中交换元素的几种方法总结

迷南。 2021-12-10 11:47 309阅读 0赞

在完成关于数组的大量算法中，基本都会涉及到元素交换，比如排序中是最常见的，一般的方法是新建一个临时变量，然后完成交换，如果给定的数组中元素是有范围的，其实还有其他方法也可以完成交换。下面就来总结一下这些方法。

### 临时变量法 ###

临时变量法是最简单的，这个不过多解释。试用任何类型的元素交换。

public static void swap(int[] a, int i, int j){ 
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

### 异或法 ###

异或运算是针对具体的每一个位相同为0，不同为1，即**1^1 = 0, 0^0 = 0, 1^0 = 1, 0^1 = 1**，  
所以对于任何整数x有**x^x = 0**, **x^0 = x** ，且运算满足结合律。所以可以用如下方法完成交换。

public static void swap(int[] a, int i, int j){ 
        a[i] = a[i] ^ a[j]; 
        a[j] = a[i] ^ a[j]; // a[j] = a[i] ^ a[j] ^ a[j] = a[i]
        a[i] = a[i] ^ a[j]; // a[i] = a[i] ^ a[j] ^ a[i] = a[j]
    }

但是这里有个问题，如果要交换的是同一个位置，即i = j, 上面代码会有问题，a\[i\] = a\[i\] ^ a\[j\] = 0，此后a\[i\] = a\[j\] = 0，不管传入时a\[i\] 等于多少，最后都等于0了。所以改进方案是交换前先判断i和j是否相等，如果不想等才交换。改进代码如下：

public static void swap(int[] a, int i, int j){ 
    	if(i != j){ 
    		a[i] = a[i] ^ a[j];
        	a[j] = a[i] ^ a[j];
        	a[i] = a[i] ^ a[j];
    	}
    }

### 加减法 ###

可以先把要交换的两个数相加，然后分别减去对方的值，也能完成交换。这里有个问题，a\[i\]+a\[j\] 有可能会越界，但是实际测试就算真的越界，还是能完成交换，可以用实际数据测试一下。

public static void swap(int[] a, int i, int j){ 
        a[i] = a[i] + a[j];
        a[j] = a[i] - a[j]; // a[j] = a[i] + a[j] - a[j]
        a[i] = a[i] - a[j]; // a[i] = a[i] + a[j] - a[i]
    }

### 乘除法 ###

既然可以用加减法，乘除法也是可以一试的，先把两个数相乘，然后分别除以对方，就能完成交换。这里也会有问题，a\[i\] \* a\[j\]也可能出现越界情况，但是实测也能得到正确结果。关键乘除法还有一个重大问题，a\[i\]和a\[j\]不能等于0，所以此方法不推荐使用。

public static void swap(int[] a, int i, int j){ 
        a[i] = a[i] * a[j];
        a[j] = a[i] / a[j];
        a[i] = a[i] / a[j];
    }

### 总结 ###

不申请临时变量的方法感觉高大上，但是每种方法总会有一些问题，所以为了保证少出问题，尽量还是使用第一种简单的申请临时变量法吧，这里列出这些方法，主要是为了开阔思维，了解更多的运算逻辑。