排序算法——对数器

àì夳堔傛蜴生んèń 2022-11-13 14:27 183阅读 0赞

# 引言 #

所谓“对数器”就是校验算法的工具程序，我们使用Math.random() 方法可以生成一个随机乱序数组，并通过Arrays.sort 来比较我们的算法是否正确。

# 代码实现 #

对数器主要是使用**对照来校验**是否正确，除了一些比较方法、拷贝方法，这里需要重点理解一下 Math.random 方法，以及如何生成一个 \[ -maxValue , maxValue \] 取值的整型数组。

public class SortChecker {
    
        public static void main(String[] args) {
            check();
        }
    
        public static void check() {
            int testTime = 50000;
            // 随机数组长度 0 ~ 100
            int maxSize = 100;
            // 值 -100 ~ 100
            int maxValue = 100;
            boolean succeed = true;
            for (int i = 0; i < testTime; i++) {
                // 原始数组
                int[] orgArr = genRandomArr(maxSize, maxValue);
                // 对照组
                int[] comprArr = Arrays.copyOf(orgArr, orgArr.length);
                // TODO:替换我的排序算法
                InsertionSort.insertionSort(orgArr);
                // 对照排序
                Arrays.sort(comprArr);
                // 比较
                if (!SortUtil.isEqual(orgArr, comprArr)) {
                    succeed = false;
                    // 打印
                    System.out.println("正确排序：");
                    SortUtil.printArr(comprArr);
                    System.out.println("我的排序：");
                    SortUtil.printArr(orgArr);
                    break;
                }
            }
            System.out.println(succeed ? "正确！" : "错误！");
        }
    
        public static int[] genRandomArr(int maxSize, int maxValue) {
            // Math.random()            -> [0, 1) 所有小数，等概率返回一个
            // Math.random() * N        -> [0, N) 所有小数，等概率返回一个
            // (int)(Math.random() * N) -> [0, N) 所有整数，等概率返回一个
            int[] arr = new int[(int) (Math.random() * (maxSize + 1))];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int)((maxValue + 1) * Math.random()) - (int)((maxValue + 1) * Math.random());
            }
            return arr;
        }
    }

/** 
     * 排序会用到的一些工具方法
     */
    public class SortUtil {
    
        public static int[] arr = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    
        public static void swap(int[] arr, int i, int j) {
            arr[i] = arr[i] + arr[j];
            arr[j] = arr[i] - arr[j];
            arr[i] = arr[i] - arr[j];
        }
    
        public static void printArr(int[] arr) {
            System.out.println();
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + "\t");
            }
        }
    
        public static boolean isEqual(int[] arr1, int[] arr2) {
            if (arr1.length != arr2.length) return false;
            for (int i = 0; i < arr1.length; i++) {
                if (arr1[i] != arr2[i]) return false;
            }
            return true;
        }
    }