quickSort修改插入排序

Question

所以我不得不做一个快速排序算法使用枢轴作为数组的中间元素。我做得很好。但现在它要求我修改quickSort算法，以便当任何子列表减少到20以下时，我使用insertionSort对子列表进行排序。

我似乎得到它的工作。它完美地编译和排序数组，但是我不知道我是否做得正确，因为修改过的快速排序和普通快速排序之间的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的旁边方法监守我必须做的不同的快速排序算法很多的。我输入了算法中使用的所有代码。让我知道如果你需要更多的感谢。

Answer 1

这看起来对我来说很好，虽然不是测试枢轴距离是否在20以下，但我会重写quicksort方法来说if (last - first <= 20) { do insertion sort} else { do normal quicksort}。这样你只需要写一次检查，而不是每次递归一次。也就是说，很可能您的基准测试实际上并没有给您提供良好的时间估计 - 也就是说，您的代码实际上可能比您想象的要快 - 仅仅因为在Java中获取准确的基准测试并不是微不足道的，也不是明显。