交换方法 | 自定义对数器
- 一、交换方法
-
-
- 方式一:常规方式,借助一个临时变量
- 方式二:使用异或实现
- 二、对数器
-
-
- 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 { 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++ ){ int[] array1 = MyComparator.generateRandomArray(maxSize, maxValue); int[] array2 = MyComparator.copyArray(array1); SelectSort.sort(array1); MyComparator.comparator(array2); 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度云软件下载中心