0

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

我似乎已经让它工作了。它完美地编译和排序数组，但是我不确定我是否做得对，因为修改后的快速排序和普通快速排序之间的 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

如果您注意到方法旁边有一堆 A、B 和 C，因为我必须做很多不同的快速排序算法。我输入了算法中使用的所有代码。让我知道你是否需要更多谢谢。

4

1 回答 1

2

这对我来说看起来非常好，尽管我不会测试枢轴距离是否最多为 20，而是将快速排序方法重写为if (last - first <= 20) { do insertion sort} else { do normal quicksort}. 这样，您只需编写一次检查，而不是为递归的每个“边”编写一次。

也就是说，您的基准测试很可能实际上并没有为您提供良好的时间估计——也就是说，您的代码实际上可能比您想象的要快——只是因为在 Java 中获得准确的基准测试并不是微不足道或显而易见的。

于 2012-04-12T23:03:12.590 回答