クイックソートのアルゴリズムがあり、その中に比較の数を返したいのですが、指定されたアルゴリズムを何も作成できません。比較フォームの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;
}
}
これを実現する最も簡単な方法Comparableは、呼び出された回数をカウントする2つのオブジェクトを比較する内部メソッドを作成し、すべての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方法を返しますcomparisons。
考慮すべきその他のヒント：
理想的には、静的メソッドと変数を使用しないでください。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);
これにより、互換性のない型を混在させていないことをコンパイル時にチェックできます。現在のraw型では、Javaはそれを行うことができません。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加