什么是对数器？
对数器简单来说通过大样本量 和 一个绝对正确的算法 来验证我们的题目是否正确。
对数器复杂一点：
1.有一个你想要测的方法a；
2.实现一个绝对正确但是复杂度不好的方法b；
3.实现一个随机样本产生器；
4.实现对比算法a和b的方法；
5.把方法a和方法b比对多次来验证方法a是否正确；
6.如果有一个样本使得比对出错，打印样本分析是哪个方法出错；
7.当样本数量很多时比对测试依然正确，可以确定方法a已经正确。
总结
通过两种不同思路的解法，然后自己生成题目要求的随机数据（这个挺费功夫的），先用第一种不同思路，但是绝对正确的算法解决，然后再用你自己写的算法解决，然后对比答案。一般绝对正确的答案，往往是那种简单的容易想到的，但是时间复杂度很差，所以重点是在正确的随机输入如何生成，这个需要勤加练习。
为什么需要对数器？
- 锻炼代码能力，对数器的各种边界条件可能没比写算法差多少
- 网上有一部分的题目是没有测试用例的，如果知道对数器你就能自己去验证你的算法正确与否
- 控制样本量来对题目进行测试，比较容易的排查出错误
package class01;
import java.util.Arrays;
public class SelectionSort {
下面是选择排序的代码，这个之前的博客里面讲过，所以这里就不详细讲了，需要的可以看这里
public static void selection(int[] arr){
// 输入整数类型的列表
if(arr == null || arr.length < 2){
// 如果输入的数组为空或者小于 2就直接返回，为空和为1都不用排序是吧？
return;
}
for(int i = 0; i < arr.length; i++) {
//遍历数组中的每一个元素，申请一个变量记录最小的元素
int minIdx = i;
for(int j = i + 1; j < arr.length; j++){
// 找到最小元素，交换
minIdx = arr[i] < arr[minIdx] ? j : minIdx;
}
swap(arr, minIdx, i);
}
}
public static void swap(int[] arr, int idxOne, int idxTwo){
// 交换两个元素
int temp = arr[idxOne];
arr[idxOne] = arr[idxTwo];
arr[idxTwo] = temp;
}
下面是对数器
我们先通过main方法来看看对数器的主要思路：
我们总共有四个步骤：生成随机数，简单方法排序，自己的实现进行排序，最后对比两者答案。
生成随机数组，我们需要明确生成数组的每个元素的取值范围，这里使用maxValue来控制，100的意思是正100到-100。
生成随机数组的长度，这里是用 maxSize来进行控制，我们这里选择生成长度为100的数组。
然后我们通过 testTime和循环来控制我们测试的次数，每次测试生成新的数组，然后用两个不同的方法进行排序和校验，然后通过一个布尔变量来告知是对是错。当我们每次测试的时候要是有数组排序出错了，我们课可以将他打印出来，进行针对性的debug。我们也可以通过调整随机输入的规模来降低我们debug的难度。
public static void main(String[] args) {
int testTime = 500000; // 测试的次数
int maxValue = 100; // 随机长度 0 ~ 100
int maxSize = 100; // 随机值 -100 ~ 100
boolean succeed = true;
for(int i = 0; i < testTime; i++){
int[] arr1 = generateRandomArray(maxSize, maxValue);// 生成一个随机数组
int[] arr2 = copyArray(arr1); // 将原来生成的随机数组，进行拷贝，开辟新的内存空间
selection(arr1); // 用你自己的方法进行排序
comparator(arr2); // 用绝对不会错的方法进行排序
if(!isEqual(arr1, arr2)){ // 对比两个答案
succeed = false;
printArray(arr1);
printArray(arr2);
break;// 有错就break
}
}
System.out.println(succeed ? "Nice" : "Error");// 最后要是程序没有错就打印Nice，错了打印Error
}
// 随机数组生成
public static int[] generateRandomArray(int maxSize, int maxValue){
// Math.random() -> [0, 1) 所有小数，等概率返回一个
// Math.random() * N -> [0, N) 所有小数，等概率返回一个
// (int)(Math.random() * N) -> [0, N - 1] 所有的整数，等概率返回一个
int[] arr = new int[(int)((maxSize + 1) * Math.random())]; // 长度随机
for(int i = 0; i < arr.length; i++){
// 随机出来的数有可能是正数有可能是负数，范围是(-maxValue, maxValue]
arr[i] = (int)((maxValue + 1) * Math.random() - (maxValue) * Math.random());
}
return arr;
}
// 第二套思路对数组进行排序
public static void comparator(int[] arr){
Arrays.sort(arr); // 直接调用语言写好的方法，稳妥！
}
// 将原数组的所有元素的内存地址复制一遍
public static int[] copyArray(int[] arr){
int[] newArray = new int[arr.length];
for(int i = 0; i < arr.length; i++){
newArray[i] = arr[i];
}
return newArray;
}
// 判断两个数组是否相等
public static boolean isEqual(int[] arr1, int[] arr2){
if((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)){
return false;
}
// 这个一定要放在计算arr.length 的上面，先检查空指针，再查看长度
if(arr1 == null && arr2 == null){
return true;
}
if(arr1.length != arr2.length){
return false;
}
for(int i = 0; i < arr1.length; i++){
if(arr1[i] != arr2[i]){
return false;
}
}
return true;
}
public static void printArray(int[] arr){
if(arr == null){
return;
}
for (int element : arr) {
System.out.print(element + ", ");
}
System.out.println();
}
}
Reference：
https://segmentfault.com/a/1190000016911927
https://italk.mashibing.com/course/detail/cour_00004003
