修改快排使用樞軸'三位數'

修改快排我試圖修改一個Quicksort程序，使用第一個元素作爲樞軸使用中位數三（中位數的第一，最後和中間元素）作爲樞軸。但是到目前爲止我的實現是在測試它時給我ArrayIndexOutOfBoundsException（s）。我想我錯過了這裏的東西，但我無法弄清楚我錯在哪裏。任何幫助和建議，高度讚賞。修改快排使用樞軸'三位數'

public class Sorts { 

    private static void swap(int[] array, int index1, int index2) { 
     // Precondition: index1 and index2 are >= 0 and < SIZE. 
     // 
     // Swaps the integers at locations index1 and index2 of the values array. 
     int temp = array[index1]; 
     array[index1] = array[index2]; 
     array[index2] = temp; 
    } 

    private static int medianOfThree(int[] array, int first, int last) { 

     int mid = array[(first+last)/2]; 

     if (array[first] > array[mid]) { 
      swap(array, first, mid); 
     } 

     if (array[first] > array[last]) { 
      swap(array, first, last); 
     } 

     if (array[mid] > array[last]) { 
      swap(array, mid, last); 
     } 
     swap(array, mid, last-1); 
     return array[last-1]; 
    } 

    private static int partition(int[] array, int first, int last, int median) { 

     int pivot = array[last-1]; 
     int saveF = last-1; 
     boolean onCorrectSide; 

     first++; 
     do { 
      onCorrectSide = true; 
      while (onCorrectSide) {   // move first toward last 
       if (array[first] > pivot) { 
        onCorrectSide = false; 
       } 
       else { 
        first++; 
        onCorrectSide = (first <= last); 
       } 
      } 

      onCorrectSide = (first <= last); 
      while (onCorrectSide) {   // move last toward first 
       if (array[last] <= pivot) { 
        onCorrectSide = false; 
       } 
       else { 
        last--; 
        onCorrectSide = (first <= last); 
       } 
      } 

      if (first < last) { 
       swap(array, first, last); 
       first++; 
       last--; 
      } 
     } while (first <= last); 

     swap(array, saveF, last); 
     return last; 
    } 


    private static void quickSort(int[] array, int first, int last) { 

     if (first < last) { 
      int pivot; 

      int median = medianOfThree(array, first, last); 
      pivot = partition(array, first, last, median); 

      // values[first]..values[splitPoint - 1] <= pivot 
      // values[splitPoint] = pivot 
      // values[splitPoint+1]..values[last] > pivot 

      quickSort(array, first, pivot - 1); 
      quickSort(array, pivot + 1, last); 
     } 
    } 


    public static void quickSort(int[] array) { 
     quickSort(array, 0, array.length-1); 
    } 
}

來源

2014-10-27 UserOrNotAnUser

哪一行會引發異常？ – csmckelvey 2014-10-27 20:21:33

@Takendarkk 線36：如果（陣列[第一]>陣列[MID]）{ ...} 線110： INT中值= medianOfThree（陣列，第一，最後一個）; line 123： quickSort（array，0，array.length-1）; – UserOrNotAnUser 2014-10-27 20:26:20

不使用變量以正確的方式：

int mid = array[first+last/2];

讓你在數組的中期價值，而不是偏移量（指數）的陣列。但是您正在使用mid，作爲您調用方法中的索引變量：

swap(array, first, mid);

來源

2014-10-27 21:10:56 user3880352

哦對！謝謝 - 我認爲那樣做了。 – UserOrNotAnUser 2014-10-29 18:37:51

修改快排使用樞軸'三位數'

回答

相關問題