對數器是什麼?
通常我們在筆試的時候或者參加編程大賽的時候，自己實現了一個演算法，但是不能夠判斷該演算法是否完全沒問題，如果在比賽平台上驗證，通常只會告訴你有沒有錯誤，出了錯不會告訴你哪裡有問題，對於排錯來說是非常坑爹的，所以對數器就橫空出世了，對數器就是用一個絕對OK的方法和隨機器生成的樣本數據進行合體，如果你的演算法是沒問題的，那麼和對數器的這個百分之百正確的方法一個元素一個元素的比較，也一定是equals的。如果返回false，說明你的演算法有問題。
我都能寫出一個百分之百正確的對數器了，還用得著跟我自己實現的演算法比較么?肯定也是對的啊，話是如此，沒錯，但是演算法的目的是更高效、更優的處理一些問題，你的比較器的時間複雜度和空間複雜度往往是比較低的，因為這樣才能保證它的準確性，而你筆試或者比賽寫出的演算法，複雜度往往比較高，所以可以通過低複雜度但是絕對正確的方法驗證你的演算法正確不正確。
對數器怎麼用?
知道了對數器是什麼之後，我們來看看應該怎麼實現一個自己的對數器，以冒泡排序為例，直接上代碼：
package com.bean.bubble_sort;
import java.util.Arrays;
public class BubbleSorted {
public static void bubbleSort(int arr[]) {
if (arr == null || arr.length < 2) {
return;
}
for (int end = arr.length-1; end > 0; end--) {
for (int i = 0; i < end; i++) {
if (arr[i] > arr[i+1]) {
swap(arr, i, i+1);
}
}
}
}
public static void swap(int[] arr, int left, int right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
//正確的排序方法
public static void rightSort(int[] arr) {
Arrays.sort(arr);
}
//生成一個隨機大小，最大數隨機的數組
public static int[] generateRandomArray(int maxSize, int maxNum) {
int[] arr = new int[(int) ((maxSize+1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random()*(maxNum+1)) - (int)(Math.random()*maxNum);
}
return arr;
}
//複製當前數組的一個樣本
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] newArray = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
newArray[i] = arr[i];
}
return newArray;
}
//判斷兩個數組是否完全相同
public static boolean isEquals(int[] arr1, int[] arr2) {
if (arr1.length != arr2.length) {
return false;
}
if (arr1 != null && arr2 == null || arr1 == null && arr2 != null) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
if (arr1 == null && arr2 == null) {
return true;
}
return true;
}
//列印數組
public static void printArray(int[] arr) {
if(arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {
int testTims = 10000;//測試次數
int maxSize = 20;//最大測試容量
int maxNum = 20;//最大測試數據
boolean euqals = true;
for (int i = 0; i < testTims; i++) {
int[] arr1 = generateRandomArray(maxSize,maxNum);
int[] arr2 = copyArray(arr1);//這兩個數組除了
//數值相同內存地址完全沒關係，請看copyArray()方法實現
bubbleSort(arr1);//用自己的演算法排序
rightSort(arr2);//用java.util.Arrays包的排序演算法排序
if (!isEquals(arr1,arr2)) {//比較是否相同
euqals = false;//一旦有不一樣的值就設為false;
break;
}
}
System.out.println(euqals ? "Success:恭喜你!沒毛病!" : "Error：抱歉，有錯誤" );//沒錯就恭喜，有錯就報錯
int[] newArr = generateRandomArray(maxSize, maxNum);
printArray(newArr);//沒排序的數組列印出來
bubbleSort(newArr);//排序後
printArray(newArr);//再次列印，程序員自己看看有沒有毛病
}
}
結果：
success：恭喜你!沒毛病!
8 2 11 8 2 -4 -5 -10 -5 3 8 13 -7 6
-10 -7 -5 -5 -4 2 2 3 6 8 8 8 11 13
代碼原理前面已經解釋的比較清楚了，不懂得話多看兩遍代碼就會了~想學會一定要動手敲!