对数器含义:生成随机样本验证算法是否正确的一种方式。
实现一个简单的对数器,用来验证 插入排序 是否正确。
public class Comparator {
/**
* 插入排序 79 98 10 68 21 15 4 33 59
* @param arr 需要排序的数组
*/
public static void insertSort(int[] arr){
int length = arr.length;
for (int end = 0; end < length; end++) {
for (int pre = end; pre > 0 && arr[pre] < arr[pre-1]; pre--) {
swap(arr,pre,pre-1);
}
}
}
/**
* 交换值
* @param arr
* @param j
* @param i
*/
private static void swap(int[] arr, int j, int i) {
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}
/**
* 生成一个长度随机 值随机的数组,最大长度位 maxLen-1,最大值 maxValue
* @param maxLen 随机数组的最大长度 < maxLen
* @param maxValue 最大随机值 < maxValue
* @return
*/
public static int[] generateRandomArr(int maxLen,int maxValue){
int arrLength = (int)(Math.random() * maxLen);
int[] arr = new int[arrLength];
for (int i = 0; i < arrLength; i++) {
arr[i] = (int) (Math.random() * maxValue);
}
return arr;
}
/**
* 复制 数组 生成一个与原数组 相同的 新数组
* @param arr
* @return
*/
public static int[] copyArray(int[] arr) {
int[] ans = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
ans[i] = arr[i];
}
return ans;
}
/**
* 对数器
* 验证 插入排序 是否正确
*/
public static boolean isSorted(int[] arr){
if(arr.length < 2){
return true;
}
int max = arr[0];
for (int i : arr) {
if(max > i){
return false;
}
max = Math.max(max,i);
}
return true;
}
/**
* 因为生成的数组长度是随机的
* 所以多次运行才能验证正确
*/
public static void main (String... args){
int maxLen = 100;
int maxValue = 1000;
int testTime = 10000;
for (int i = 0; i < testTime; i++) {
int[] arr = generateRandomArr(maxLen, maxValue);
int[] source = copyArray(arr);
insertSort(arr);
if(!isSorted(arr)){
System.out.println("插入排序错误!");
//打印原数组的值
for (int j = 0; j < source.length; j++) {
System.out.print(source[j] + " ");
}
//出错跳出循环
break;
}
}
}
}