2016-01-15 99 views
0

我用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%的性能

,但實際發生的事情是,我已經做了這個測試很多次,幾乎總是讓上優化的一個

正常快速排序更好的結果究竟什麼是錯的第二個實施

+0

你會得到什麼樣的時間?你有沒有嘗試通過探查器運行它,以查找是否有任何明顯的東西? – Krease

+1

你從哪裏得到5%的數字?這將高度依賴於輸入數據。否則,請參閱傑里科芬的答案。 –

回答

2

三者的中位數(或更多)對於隨機排序的輸入通常會比較慢。

中位數爲3意在幫助防止非常糟糕的情況變得非常可怕。無論如何,有很多方法可以使它變得非常糟糕,但至少可以避免一些常見排序問題 - 例如,選擇第一個元素,因爲如果/當(大部分)輸入已經排序時,樞軸可能會產生可怕的結果。