交换方法 | 自定义对数器

• 一、交换方法
• • • 方式一：常规方式，借助一个临时变量
    • 方式二：使用异或实现
• 二、对数器
• • • 1、对数器概念
    • 2、自定义对数器
    • 3、对数器的使用
    • 4、测试结果

一、交换方法

• 交换数组中两个索引位置的元素。

方式一：常规方式，借助一个临时变量

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

• array ：数组名； i ，j ：需要交换位置的两个索引下标。
• 该方式的实现思想就是先将 i 位置上的元素存入临时变量 temp 中，然后用 j 位置的元素覆盖 i 位置，最后将 temp 的值再赋值给 j 位置。

方式二：使用异或实现

• 在使用异或实现交换操作之前，我们需要先简单了解一下什么是异或。
• 首先，" ^ "符号表示异或运算。异或运算使用二进制（0或1）实现，如果两个数在同一位置全是 0 或 全是1，则异或后得到 0 ；如果同一位置数字不同，则得到 1 。简单来说就是，相同得0，不同得1。
• 可以结合下述例子，更加深刻的理解"相同得0，不同得1"。
  
• 清楚了什么是异或之后，我们还需要了解一些异或的性质。假设有一个数 a 。
  • a ^ 0 = a。a 与 0 异或还是 a 。
    
• a ^ a = 0。a 与自己异或得 0 。
  
• 异或满足交换律，即 a ^ b = b ^ a。
• 异或满足结合律，即 (a ^ b) ^ a = a ^ (b ^ a)。
• 有了上述了解之后，我们再来分析如何使用异或来实现交换操作，先抛出实现代码。

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

• 使用 a 代替 array[i] ，使用 b 代替 array[j]。
  
  每执行完一行代码，a 或 b 所对应的值是会发生变化的。
• 使用异或实现交换需要注意一点，传入的 i 和 j 不能是相等的，因为如果是数组同一个位置交换，就相当于 a ^ a，得到的结果是 0 ，是不符合交换要求的。
• 这也提醒我们，只有我们在能确定 i 和 j 一定不等时，才可以使用异或方式。如果无法保证，就使用方式一。

二、对数器

• 通常情况下，我们都是在一些网站上刷算法题，在上面编写代码，提交后，后台会提供测试用例来验算代码的正确性，但是如果我们做书本上或试卷上的算法题时，没有后台给我们提供测试用例，我们很难确定自己所写代码的正确性，这个时候对数器就能够充当后台给我们提供测试用例。
• 对于一道算法题，如果在不考虑时间复杂度的情况下，我们可以使用最笨最暴力的方法来实现，但是如果我们想优化自己的代码，就可以使用对数器来比较两种方法得到的结果是否是一致的，如果是一致的，则表示优化代码是正确的。
• 说了这么多，就是想告诉大家，自己手动设计一个对数器，是非常重要的。

1、对数器概念

• 定义两种方法。
  • 方法一确定是正确的方法。
  • 方法二是用来验证正确性的方法。
• 定义随机样本产生器，其实就是一个定义一个随机产生样本的方法。
• 将同一个测试用例分别用方法一和方法二测试，看最后得到的结果是否是相同的，如果相同，则表示方法二是正确的。

2、自定义对数器

• 本篇文章所定义的对数器仅适用于判断数组的排序算法。如果想要测试其他算法，可以根据实际需求仿照该方法自己编写。

public class MyComparator {    // 调用Arrays工具类提供的sort方法，来完成对数组的排序。    // 该方法作为对数器概念中的方法一，一定是正确的    public static void comparator( int[] array ){ Arrays.sort(array);    }    // 定义随机样本产生器    public static int[] generateRandomArray( int maxSize , int maxValue ){   // 随机定义数组长度 int[] array = new int[ (int)(Math.random() * maxSize) ];     for ( int i = 0; i < array.length; i++ ){     // 随机定义数组元素值     array[i] = (int)(Math.random() * maxValue) - (int)(Math.random() * maxValue); } return array;    }    // 复制数组    public static int[] copyArray( int[] array ){ if ( array == null){     return null; } int[] res = new int[array.length]; for ( int i = 0; i < array.length; i++ ){     res[i] = array[i]; } return res;    }    // 判断两个数组中各个位置的元素值是否相同    public static boolean isEqual( int[] array1 , int[] array2 ){ if ( array1 == null && array2 == null ){     return true; } if ( ( array1 == null && array2 != null ) || ( array1 != null && array2 == null ) ){     return false; } if ( array1.length != array2.length ){     return false; } for ( int i = 0; i < array1.length; i++ ){     if ( array1[i] != array2[i] ){  return false;     } } return true;    }    // 打印数组元素    public static void printArray( int[] array ){ if ( array == null ){     return; } for ( int num : array ){     System.out.print( num + "\t" ); } System.out.println();    }}

3、对数器的使用

• 借用选择排序来演示如何使用对数器

public class SelectSort {// 交换方法    public static void swap( int[] array , int i , int j ){ int temp = array[i]; array[i] = array[j]; array[j] = temp;    }// 选择排序方法，该方法相当于对数器概念中的方法二，是待验证正确性的方法    public static void sort( int[] array ){ if ( array == null || array.length < 2){     return; } for ( int i = 0; i < array.length; i++ ){     int minIndex = i;     for ( int j = i + 1 ; j < array.length; j++ ){  if ( array[j] < array[minIndex] ){      minIndex = j;  }     }     swap( array , i , minIndex); }    }    public static void main(String[] args) {    // 数组最大长度 int maxSize = 100; // 数组元素最大值 int maxValue = 100; // 测试次数 int testTime = 5000000; // 是否正确 boolean ret = true; for ( int i = 0; i < testTime; i++ ){ // 调用自定义对数器中的generateRandomArray方法随机产生样本     int[] array1 = MyComparator.generateRandomArray(maxSize, maxValue);     // 将array1中的元素复制给array2     int[] array2 = MyComparator.copyArray(array1);     // SelectSort类中定义的sort方法相当于对数器概念中的方法二，是待验证正确性的算法     // 使用该方法对array1数组排序     SelectSort.sort(array1);     // 对array2数组排序，排序后的结果一定是正确的     MyComparator.comparator(array2);     // 判断两个数组排序后的结果是否相同，如果相同则表示方法二实现代码正确，即SelectSort类的sort方法实现正确     if ( !MyComparator.isEqual(array1,array2) ){  ret = false;  MyComparator.printArray(array1);  System.out.println();  MyComparator.printArray(array2);  break;     } } System.out.println( ret ? "Success" : "Fail");    }}

4、测试结果

8度云软件下载中心