algorithm - 优化快速排序

Question

我正在用 java 实现快速排序算法，代码如下:

public class quickSort {
      private int array[];
    private int length;

    public void sort(int[] inputArr) {

        if (inputArr == null || inputArr.length == 0) {
            return;
        }
        this.array = inputArr;
        length = inputArr.length;
        quickSorter(0, length - 1);
    }

    private void quickSorter(int lowerIndex, int higherIndex) {

        int i = lowerIndex;
        int j = higherIndex;

        // calculate pivot number, I am taking pivot as middle index number
        int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
        // Divide into two arrays
        while (i <= j) {

            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                exchangeNumbers(i, j);
                //move index to next position on both sides
                i++;
                j--;
            }
        }
        // call quickSort() method recursively
        if (lowerIndex < j)
            quickSorter(lowerIndex, j);
        if (i < higherIndex)
            quickSorter(i, higherIndex);
    }

    private void exchangeNumbers(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

}

然后我用(三的中位数)实现它

public class quickSort {
      private int array[];
private int length;

public void sort(int[] inputArr) {

    if (inputArr == null || inputArr.length == 0) {
        return;
    }
    this.array = inputArr;
    length = inputArr.length;
    quickSorter(0, length - 1);
}

private void quickSorter(int lowerIndex, int higherIndex) {

    int i = lowerIndex;
    int j = higherIndex;
    int mid = lowerIndex+(higherIndex-lowerIndex)/2;
    if (array[i]>array[mid]){
       exchangeNumbers( i,  mid);
    }
    if (array[i]>array[j]){
       exchangeNumbers( i,  j);
    }
    if (array[j]<array[mid]){
       exchangeNumbers( j, mid);
    }

    int pivot = array[mid];
    // Divide into two arrays
    while (i <= j) {

        while (array[i] < pivot) {
            i++;
        }
        while (array[j] > pivot) {
            j--;
        }
        if (i <= j) {
            exchangeNumbers(i, j);
            //move index to next position on both sides
            i++;
            j--;
        }
    }
    // call quickSort() method recursively
    if (lowerIndex < j)
        quickSorter(lowerIndex, j);
    if (i < higherIndex)
        quickSorter(i, higherIndex);
}

private void exchangeNumbers(int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}
}

和测试主要:

public static void main(String[] args) {
        File number = new File ("f.txt");
        final int size = 10000000;

        try{
            quickSortOptimize opti = new quickSortOptimize();
             quickSort s = new quickSort();
        PrintWriter printWriter  = new PrintWriter(number);
         for (int i=0;i<size;i++){
            printWriter.println((int)(Math.random()*100000));
        }
         printWriter.close();
        Scanner in = new Scanner (number);
        int [] arr1 = new int [size];
        for (int i=0;i<size;i++){
          arr1[i]=Integer.parseInt(in.nextLine());
        }
        long a=System.currentTimeMillis();
        opti.sort(arr1);
        long b=System.currentTimeMillis();
        System.out.println("Optimaized quicksort: "+(double)(b-a)/1000);
        in.close();
        int [] arr2 = new int [size];
        Scanner in2= new Scanner(number);
        for (int i=0;i<size;i++){
          arr2[i]=Integer.parseInt(in2.nextLine());
        }
         long c=System.currentTimeMillis();
         s.sort(arr2); 
        long d=System.currentTimeMillis();
         System.out.println("normal Quicksort: "+(double)(d-c)/1000);
        }catch (Exception ex){ex.printStackTrace();}

    }

问题是这种优化方法应该能提高5%的性能

但是，实际发生的是，我已经多次进行了此测试，并且几乎总是在优化一个的普通快速排序上获得更好的结果

那么第二个实现有什么问题

Answer 1

对于随机排序的输入，三(或更多)的中位数通常会较慢。

三的中位数旨在帮助防止一个非常糟糕的案例变得非常可怕。无论如何，有一些方法可以让它变得非常糟糕，但至少可以避免一些常见排序的问题——例如，如果/当(大部分)输入已经排序时，选择第一个元素作为基准会产生糟糕的结果。