JAVA--归并排序算法和插入排序算法，性能测试对比

public class SortTestHelper {

    // 测试插入排序算法的时间
    public void testSort(int arr[], int n) {
 InsertionSort is = new InsertionSort();

 long startTime = System.currentTimeMillis();    //获取开始时间
 is.insertionSort(arr, n);
 long endTime = System.currentTimeMillis();    //获取结束时间

 System.out.println("n" + "InsertionSort 共耗时：" + (endTime - startTime) + "ms");
    }

    // 测试归并排序算法的时间
    public void testSort2(int arr[], int n) {
 MergeSort is = new MergeSort();

 long startTime = System.currentTimeMillis();    //获取开始时间
 is.mergeSort(arr, n);
 long endTime = System.currentTimeMillis();    //获取结束时间

 System.out.println("n" + "MergeSort 共耗时：" + (endTime - startTime) + "ms");
    }

    // 随机生成int数组
    public int[] generateRandomArray(int n) {

 int[] result = new int[n];

 for (int i = 0; i < n; i++) {
     result[i] = (int) (Math.random() * n);
 }
 return result;
    }

    // 生成近乎有序的int数组
    public int[] generateNearlyOrderedArray(int n, int swapTimes) {
 int[] arr = new int[n];
 for (int i = 0; i < n; i++) {
     arr[i] = i;
 }

 int temp;
 for (int j = 0; j < swapTimes; j++) {
     int x = (int) Math.random() * n;
     int y = (int) Math.random() * n;
     temp = arr[x];
     arr[x] = arr[y];
     arr[y] = temp;
 }
 return arr;
    }

}

public class InsertionSort {

    public void insertionSort(int arr[], int n) {

 for (int i = 1; i < n; i++) {

     int temp = arr[i];
     int j;
     for (j = i; j > 0 && arr[j - 1] > temp; j--) {
  arr[j] = arr[j - 1];
     }
     arr[j] = temp;
 }

    }

}

public class MergeSort {

    
    public static void __merge(int[] arr, int left, int mid, int right) {

 int[] aux = new int[right - left + 1];

 for (int i = left; i <= right; i++) {
     aux[i - left] = arr[i];
 }

 int i = left, j = mid + 1;

 for (int k = left; k <= right; k++) {

     if (i > mid) {
  arr[k] = aux[j - left];
  j++;
     } else if (j > right) {
  arr[k] = aux[i - left];
  i++;
     } else if (aux[i - left] < aux[j - left]) {
  arr[k] = aux[i - left];
  i++;
     } else {
  arr[k] = aux[j - left];
  j++;
     }
 }
    }

    
    public static void __mergeSort(int[] arr, int left, int right) {

 
// if (left >= right) {
//     return;
// }
 if (right - left <= 15) {
     InsertionSort is = new InsertionSort();
     is.insertionSort2(arr, left, right);
     return;
 }

 int mid = (left + right) / 2;
 __mergeSort(arr, left, mid);
 __mergeSort(arr, mid + 1, right);

 
 if (arr[mid] > arr[mid + 1]) {
     __merge(arr, left, mid, right);
 }
// __merge(arr, left, mid, right);

    }

    public static void mergeSort(int[] arr, int n) {

 __mergeSort(arr, 0, n - 1);
    }

    public static void main(String[] args) {
 SortTestHelper sth = new SortTestHelper();

 // 测试1：测试乱序的数组
 int n = 80000;
// int[] array = sth.generateRandomArray(n);
// // 对插入排序算法和归并排序算法，性能进行测试对比
// sth.testSort(array, n);
// sth.testSort2(array, n);

 // 测试2：测试近乎有序的数组
 int swapTimes = 10;
 int[] array1 = sth.generateNearlyOrderedArray(n, swapTimes);
 // 对插入排序算法和归并排序算法，性能进行测试对比
 sth.testSort(array1, n);
 sth.testSort2(array1, n);
    }
}

InsertionSort 共耗时：3ms

MergeSort 共耗时：4ms