【Java】用于测试排序算法执行效率的简单测试程序---------基于整型数组

【Java】用于测试排序算法执行效率的简单测试程序---------基于整型数组

1.generateRandomArray(int n, int left, int right)

该方法可以生成一个元素值在[left,right]区间内且随机，长度为n的整型数组；

2.generateSoredArray(int n, int times)

该方法可用于生成一个长度为n且近乎有序的整型数组；首先生成一个数据为0~n- 1的有序数组，然后在索引区间内生成两个随机数并交换对应元素值；times为随机交换的次数，交换次数越少，数组越近乎有序，反之亦然；

3.testSort(String sortName, int[] arr)

该方法根据方法名称调用相应的排序方法对arr数组进行排序操作，涉及到反射相关知识

4.isSorted(int[] arr)

该方法用于检验排序后的数组是否真的有序

5.arrCopy(int[] arr)

该方法用于深拷贝arr数组，保证测试过程中数据统一

public class SortHelper {
    //获取随机数的对象
    private static final ThreadLocalRandom random = ThreadLocalRandom.current();
    //在区间[left,right]上生成n个随机数，返回随机数组
    public static int[] generateRandomArray(int n, int left, int right) {
        int[] arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(left, right);
        }
        return arr;
    }
    
    public static int[] generateSoredArray(int n, int times) {
        int[] arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }
        for (int j = 0; j <= times; j++) {
            int a = random.nextInt(n);
            int b = random.nextInt(n);
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
        return arr;
    }
    // 根据传入的方法名称就能调用这个方法，需要借助反射
    // 根据方法名称调用相应的排序方法对arr数组进行排序操作
    public static void testSort(String sortName, int[] arr) {
        //SevenSort是包含排序方法的类名
        Class cls = SevenSort.class;
        try {
            Method method = cls.getDeclaredMethod(sortName, int[].class);
            //算法开始执行时间
            long start = System.nanoTime();
            method.invoke(null, arr);
            //算法执行结束时间
            long end = System.nanoTime();
            if (isSorted(arr)) {
                // 算法正确
                System.out.println(sortName + "排序结束,共耗时:" + (end - start) / 1000000.0 + "ms");
            }
        } catch (NoSuchMethodException | InvocationTargetException | IllegalAccessException e) {
            e.printStackTrace();
        }
    }
    //判断算法是否正确
    private static boolean isSorted(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                System.err.println("sort error !!!");
                return false;
            }
        }
        return true;
    }
    // 生成一个arr的深拷贝数组
    // 为了测试不同排序算法的性能，需要在相同的数据集上进行测试
    public static int[] arrCopy(int[] arr) {
        return Arrays.copyOf(arr, arr.length);
    }
}

    public static void main(String[] args) {
        //数组长度10万
        int n = 100000;
        //生成一个近乎有序数组，10万个元素仅有10对进行交换值
        int[] arr1 = Helper.generateSoredArray(n, 10);
        //生成一个随机且无大量重复值的数组
        int[] arr2 = Helper.generateRandomArray(n, 0, 100000);
        //分别拷贝上述两个数组
        int[] copyArr11 = Helper.arrCopy(arr1);
        int[] copyArr12 = Helper.arrCopy(arr1);
        int[] copyArr13 = Helper.arrCopy(arr1);
        int[] copyArr21 = Helper.arrCopy(arr2);
        int[] copyArr22 = Helper.arrCopy(arr2);
        int[] copyArr23 = Helper.arrCopy(arr2);
        //测试选择排序、直接插入排序、折半插入排序处理近乎有序数组所需时间
        System.out.println("选择排序、直接插入排序、折半插入排序处理近乎有序数组所需时间");
        Helper.testSort("selectionSort", copyArr11);
        Helper.testSort("insertionShort", copyArr12);
        Helper.testSort("insertionShortHalf", copyArr13);
        System.out.println("--------------------------------------------------");
        //测试选择排序、直接插入排序、折半插入排序处理随机数组所需时间
        System.out.println("选择排序、直接插入排序、折半插入排序处理随机数组所需时间");
        Helper.testSort("selectionSort", copyArr21);
        Helper.testSort("insertionShort", copyArr22);
        Helper.testSort("insertionShortHalf", copyArr23);
    }
	//执行结果
	选择排序、直接插入排序、折半插入排序处理近乎有序数组所需时间
	selectionSort排序结束,共耗时:8266.8289ms
	insertionShort排序结束,共耗时:12.1766ms
	insertionShortHalf排序结束,共耗时:11.1459ms
	--------------------------------------------------
	选择排序、直接插入排序、折半插入排序处理随机数组所需时间
	selectionSort排序结束,共耗时:10079.0159ms
	insertionShort排序结束,共耗时:4389.6981ms
	insertionShortHalf排序结束,共耗时:1654.5927ms