冒泡排序、选择排序、插入排序

import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

public class BasicSort {
    private static BasicSort basicSort = new BasicSort();

    private static void swap(int[] arr, int x, int y) {
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }

    public void bubbleSort(int[] arr) {
        // System.out.println("bubble sort" + arr);
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
        // System.out.println(Arrays.toString(arr));
    }

    public void insertSort(int[] arr) {
        // System.out.println("insert sort" + arr);
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                // 合适的位置就是自己右边的都比自己大
                if (arr[j] < arr[j - 1]) {
                    swap(arr, j, j - 1);
                }
            }
        }
        // System.out.println(Arrays.toString(arr));
    }

    public void insertSort2(int[] arr) {
        // System.out.println("insert sort" + arr);
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int idx = i - 1;
            while (idx >= 0 && arr[idx] > tmp) {
                idx--;
            }
            // 循环执行结束后，idx指向第一个小于等于tmp的位置
            for (int j = i; j > idx + 1; j--) {
                arr[j] = arr[j - 1];
            }
            arr[idx + 1] = tmp;
        }
        // System.out.println(Arrays.toString(arr));
    }

    public void selectSort(int[] arr) {
        // System.out.println("select sort" + arr);
        for (int i = 0; i < arr.length - 1; i++) {
            int idx = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[idx]) {
                    idx = j;
                }
            }
            swap(arr, i, idx);
        }
        // System.out.println(Arrays.toString(arr));
    }

    public static void runBenchMark(int size, int min, int max, boolean validate, long seed,
            List<String> methodStringList) throws Exception {
        Random random = new Random(seed);
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            // arr[i] = (int) ((max - min) * Math.random()) + min;
            arr[i] = random.nextInt(min, max);
        }
        int[] standard = Arrays.copyOf(arr, arr.length);
        long startTime = System.currentTimeMillis();
        Arrays.sort(standard);
        long endTime = System.currentTimeMillis();
        String duration = (endTime - startTime) / 1000.0 + " ms\n";
        StringBuilder sb = new StringBuilder();
        sb.append(duration);
        // System.out.println(Arrays.toString(arr));
        for (String methodString : methodStringList) {
            sb.append(methodString + "\t");
            Class[] parameterTypes = new Class[] { int[].class };// 只有方法名不能唯一确定一个方法的存在
            Method method = BasicSort.class.getMethod(methodString, parameterTypes);
            int[] mine = Arrays.copyOf(arr, arr.length);
            startTime = System.currentTimeMillis();
            method.invoke(basicSort, mine);
            endTime = System.currentTimeMillis();
            duration = (endTime - startTime) / 1000.0 + " ms\t";
            sb.append(duration);
            if (validate) {
                boolean flag = Arrays.equals(mine, standard);
                sb.append(flag + "\n");
            }
        }
        System.out.println(sb.toString());
    }

    public static void main(String[] args) throws Exception {
        // 2^16
        runBenchMark(Integer.MAX_VALUE >> 16, 0, 100, true, 114514,
                List.of("bubbleSort", "insertSort", "insertSort2", "selectSort"));
    }
}