quickSort修改插入排序

所以我不得不做一個快速排序算法使用樞軸作爲數組的中間元素。我做得很好。但現在它要求我修改quickSort算法，以便當任何子列表減少到20以下時，我使用insertionSort對子列表進行排序。quickSort修改插入排序

我似乎得到它的工作。它完美地編譯和排序數組，但是我不知道我是否做得正確，因爲修改過的快速排序和普通快速排序之間的CPU時間差異並不是那麼不同。我的不確定性是在遞歸方法recQuickSortC中，我有「> = 20」語句。我不確定這是否是實施修改的正確方法，它可能是完全錯誤的，我所知道的是它正確地排序它。任何幫助將很好，謝謝。

這裏是我的修改快速排序算法：

public void quickSortC(T[] list, int length) 
{ 
    recQuickSortC(list, 0, length - 1); 
}//end quickSort 

private void recQuickSortC(T[] list, int first, int last) 
{ 
    if (first < last) 
    { 
     int pivotLocation = partitionA(list, first, last); 
     if ((pivotLocation - 1) >= 20) 
      recQuickSortC(list, first, pivotLocation - 1); 
     else 
      insertionSort(list,pivotLocation -1); 

     if ((pivotLocation - 1) >= 20) 
      recQuickSortC(list, pivotLocation + 1, last); 
     else 
      insertionSort(list, pivotLocation + 1); 
    } 
}//end recQuickSort 

private int partitionA(T[] list, int first, int last) 
{ 
    T pivot; 

    int smallIndex; 

    swap(list, first, (first + last)/2); 

    pivot = list[first]; 
    smallIndex = first; 

    for (int index = first + 1; index <= last; index++) 
    { 
     if (list[index].compareTo(pivot) < 0) 
     { 
      smallIndex++; 
      swap(list, smallIndex, index); 
     } 
    } 

    swap(list, first, smallIndex); 

    return smallIndex; 
}//end partition 


    public void insertionSort(T[] list, int length) 
{ 
    for (int unsortedIndex = 1; unsortedIndex < length; 
           unsortedIndex++) 
    { 
     Comparable<T> compElem = 
        (Comparable<T>) list[unsortedIndex]; 

     if (compElem.compareTo(list[unsortedIndex - 1]) < 0) 
     { 
      T temp = list[unsortedIndex]; 

      int location = unsortedIndex; 

      do 
      { 
       list[location] = list[location - 1]; 
       location--; 
      } 
      while (location > 0 && 
        temp.compareTo(list[location - 1]) < 0); 

      list[location] = (T) temp; 
     } 
    } 
}//end insertionSort

如果您發現孤單一幫一的，B公司和C的旁邊方法監守我必須做的不同的快速排序算法很多的。我輸入了算法中使用的所有代碼。讓我知道如果你需要更多的感謝。

來源

2012-04-12 user1210259

這看起來對我來說很好，雖然不是測試樞軸距離是否在20以下，但我會重寫quicksort方法來說if (last - first <= 20) { do insertion sort} else { do normal quicksort}。這樣你只需要寫一次檢查，而不是每次遞歸一次。也就是說，很可能您的基準測試實際上並沒有給您提供良好的時間估計 - 也就是說，您的代碼實際上可能比您想象的要快 - 僅僅因爲在Java中獲取準確的基準測試並不是微不足道的，也不是明顯。

來源

2012-04-12 23:03:12

此外：關於正確的Java微型基準測試的必需鏈接[這裏]（http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java） – Voo 2012-04-12 23:04:41

獲得準確的Java基準的最簡單方法是使用[Caliper]（http://caliper.googlecode.com），它只是爲您處理所有「難題」。 – 2012-04-12 23:05:16

一個很好的工具來處理很多問題，但仍有很多事情不是（並且imho不能）在那裏自動化，所以您仍然必須瞭解JVM實際執行的操作。 – Voo 2012-04-12 23:07:12

quickSort修改插入排序

回答

相關問題