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");
    }

    // 测试快速排序算法的时间
    public void testSort3(int arr[], int n) {
 QuickSort is = new QuickSort();

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

 System.out.println("n" + "QuickSort 共耗时：" + (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 * 10));
 }
 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 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 class QuickSort {

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

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

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

 if (left >= right) {
     return;
 }

 int p = __partition(arr, left, right);
 __quickSort(arr, left, p - 1);
 __quickSort(arr, p + 1, right);

    }

    
    public int __partition(int[] arr, int left, int right) {

 int v = arr[left];
 int temp;
 // arr[left+1...j] < v ; arr[j+1...i) > v
 int j = left;
 for (int i = j + 1; i <= right; i++) {
     if (arr[i] < v) {
  temp = arr[i];
  arr[i] = arr[j + 1];
  arr[j + 1] = temp;
  j++;
     }
 }
 temp = arr[j];
 arr[j] = arr[left];
 arr[left] = temp;

 return j;
    }

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

 int n = 1000000;
 int[] array = sth.generateRandomArray(n);

 sth.testSort2(array, n);
 sth.testSort3(array, n);

// for (int y: array) {
//     System.out.println(y + " ");
// }
    }

}

MergeSort 共耗时：235ms

QuickSort 共耗时：160ms