對數器
對數器的實現：
- 你想要測的方法a（最優解）
- 實現復雜度不好但是容易實現的方法b（暴力解）
- 實現一個隨機樣本產生器（長度也隨機、值也隨機）
- 把方法a和方法b跑相同的輸入樣本，看看得到的結果是否一樣
- 如果有一個隨機樣本使得比對結果不一致，打印這個出錯的樣本進行人工干預，改對方法a和方法b
- 當樣本數量很多時比對測試依然正確，可以確定方法a（最優解）已經正確。
關鍵是第5步，找到一個數據量小的錯誤樣本，便于你去帶入debug
然后把錯誤例子帶入代碼一步一步排查
Print大法、斷點技術都可以
對數器的門檻其實是比較高的，因為往往需要在兩種不同思路下實現功能相同的兩個方法，暴力一個、想象中的最優解是另一個。
以后的很多題目都用到對數器，幾乎可以驗證任何方法，尤其在驗證貪心、觀察規律方面很有用。
public static void main(String[] args){// 隨機數組最大長度int N = 100;// 隨機數組每個值，在1~V之間隨機int V = 1000;// testTimes : 測試次數int testTimes = 50000;System.out.println("測試開始");for (int i = 0; i < testTimes; i++){// 隨機得到一個長度，長度在[0~N-1]int n = (int) (Math.random() * N);// 得到隨機數組int[] arr = randomArray(n, V);int[] arr1 = copyArray(arr);int[] arr2 = copyArray(arr);int[] arr3 = copyArray(arr);selectionSort(arr1);bubbleSort(arr2);insertionSort(arr3);if (!sameArray(arr1, arr2 ) || !sameArray(arr1, arr3)){System.out.println("出錯了！");// 當有錯了// 打印是什么例子，出錯的// 打印三個功能，各自排序成了什么樣// 可能要把例子帶入}}System.out.println("測試結束");
}// 為了驗證
// 得到一個隨機數組，長度是n
// 數組中每個數，都在1~v之間，隨機得到
public static int[] randomArray(int n, int v){int[] arr = new int[n];for (int i = 0; i < n; i++){// Math.random() -> double -> [0,1)一個小數，0.37463473126、0.001231231// Math.random() * v -> double -> [0,v)一個小數，依然等概率// (int)(Math.random() * v) -> int -> 0 1 2 3 ... v-1，等概率的！// (int)(Math.random() * v) + 1 -> int ->1 2 3 ... v，等概率的！arr[i] = (int)(Math.random() * v) + 1;}return arr;
}// 為了驗證
// 拷貝數組
public static int[] copyArray(int[] arr){int n = arr.length;int[] ans = new int[n];for (int i = 0; i < n; i++){ans[i] = arr[j];}return ans;
}// 為了驗證
// 驗證數組是否一樣
public static boolen sameArray(int[] arr1, int[] arr2){int n = arr1.length;for (int i = 0; i < n; i++){if (arr1[i] != arr2[i]){return false;}}return true;
}....
