优化快速排序

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

对于

随机排序的输入，中位数为 3（或更多）通常会较慢。

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