java - 查找此特定快速排序算法中的比较次数

Question

我有一个快速排序算法，我想返回其中的比较次数，但我无法对给定的算法进行任何处理。我必须返回比较形式 getCompares() 函数。我在网上查了很多地方，但没有找到合适的解决方案。没有。的比较 已排序大小为 100 的数据应给出 488 作为结果。

/**
 * Quicksort algorithm.
 * @param a an array of Comparable items.
 */

public static void QuickSort( Comparable [ ] a )

{
    quicksort( a, 0, a.length - 1 );
}

private static final int CUTOFF = 10;

/**
 * Method to swap to elements in an array.
 * @param a an array of objects.
 * @param index1 the index of the first object.
 * @param index2 the index of the second object.
 */
public static final void swapReferences( Object [ ] a, int index1, int index2 )
{
    Object tmp = a[ index1 ];
    a[ index1 ] = a[ index2 ];
    a[ index2 ] = tmp;
}

/**
 * Internal quicksort method that makes recursive calls.
 * Uses median-of-three partitioning and a cutoff of 10.
 * @param a an array of Comparable items.
 * @param low the left-most index of the subarray.
 * @param high the right-most index of the subarray.
 */
private static void quicksort( Comparable [ ] a, int low, int high )
{
    if( low + CUTOFF > high )
        insertionSort( a, low, high );
    else
    {
            // Sort low, middle, high
        int middle = ( low + high ) / 2;
        if( a[ middle ].compareTo( a[ low ] ) < 0 )
            swapReferences( a, low, middle );
        if( a[ high ].compareTo( a[ low ] ) < 0 )
            swapReferences( a, low, high );
        if( a[ high ].compareTo( a[ middle ] ) < 0 )
            swapReferences( a, middle, high );

            // Place pivot at position high - 1
        swapReferences( a, middle, high - 1 );
        Comparable pivot = a[ high - 1 ];

            // Begin partitioning
        int i, j;
        for( i = low, j = high - 1; ; )
        {
            while( a[ ++i ].compareTo( pivot ) < 0 )
                ;
            while( pivot.compareTo( a[ --j ] ) < 0 )
                ;
            if( i >= j )
                break;
            swapReferences( a, i, j );
        }

            // Restore pivot
        swapReferences( a, i, high - 1 );

        quicksort( a, low, i - 1 );    // Sort small elements
        quicksort( a, i + 1, high );   // Sort large elements
    }
}

/**
 * Internal insertion sort routine for subarrays
 * that is used by quicksort.
 * @param a an array of Comparable items.
 * @param low the left-most index of the subarray.
 * @param n the number of items to sort.
 */
private static void insertionSort( Comparable [ ] a, int low, int high )
{
    for( int p = low + 1; p <= high; p++ )
    {
        Comparable tmp = a[ p ];
        int j;

        for( j = p; j > low && tmp.compareTo( a[ j - 1 ] ) < 0; j-- )
            a[ j ] = a[ j - 1 ];
        a[ j ] = tmp;
    }
}

Answer 1

实现此目的的最简单方法是创建一个内部方法来比较 2 个 Comparable 对象，该方法计算调用次数并替换所有 compareTo 调用调用该方法。

private int comparisons = 0;

private int compare(Comparable<?> obj1, Comparable<?> obj2) {
    comparisons++;
    return obj1.compareTo(obj2);
}

然后将 tmp.compareTo(a[j-1]) 等表达式替换为 compare(tmp, a[j-1])。

您的 getCompares 方法将返回比较。

需要考虑的其他一些技巧:

理想情况下不要使用静态方法和变量。制作一个 QuickSort 类，在使用前需要实例化。

最好不要使用原始类型(例如代码中的Comparable)。大多数现代 IDE 都会正确地警告这种危险。使用通配符(如上所述)，或者更好的是，实际上向您的 QuickSort 类添加泛型类型:

class QuickSort<T extends Comparable<T>> {
    public void sort(T[] array) { ... }
}

QuickSort<Integer> intSorter = new QuickSort<>();
int[] array = {5, 8, 2};
intSorter.sort(array);

这将允许编译时检查您没有混合不兼容的类型。您当前的原始类型不允许 Java 执行此操作。