2

私は与えられたクイックソートアルゴリズムを改善するように頼まれました：

public void quickSort(Comparable[] a, int left, int right) {
// Sort a[left…right] into ascending order.
    if (left < right) {
        int p = partition(a, left, right);
        quickSort(a, left, p-1);
        quickSort(a, p+1, right);   
    }
}    




public int partition(Comparable[] a, int left, int right) {
// Partition a[left…right] such that  
// a[left…p-1] are all less than or equal to a[p] 
// and a[p+1…right] are all greater than or equal to 
// a[p]. Return p.
    Comparable pivot = a[left];
    int p = left;
    for (int r = left+1; r <= right; r++) {
        int comp = a[r].compareTo(pivot);
        if (comp < 0) {
            a[p] = a[r];  a[r] = a[p+1];
            a[p+1] = pivot;  p++;
        }
    }
    return p;
}

...以下の疑似コード命令を使用して、初期アルゴリズムよりも少ないコピー数で動作できるようにします。

To partition a[left…right] such that a[left…j–1] are all less than or equal to a[j], 
and a[j+1…right] are all greater than or equal to a[j]:
1.  Set pivot to a[left].
2.  Set i = left + 1 and j = right.
3.  While i <= j, repeat:
    3.1.    While i <= j and a[i] <= pivot, increment i. 
    3.2.    While j >= i and a[j] >= pivot, decrement j.
    3.3.    If i < j, swap a[i] and a[j].
4.  If j != left, set a[left] to a[j], and a[j] to pivot. 
5.  Terminate with answer j.

問題は、このビットを整理できないことです。

While i <= j and a[i] <= pivot,

Comparableで<および>記号を使用できないというエラーメッセージが表示されるため。オンラインで解決策をいくつか見つけましたが、どれもうまくいきませんでした。

何か案は？このプロジェクトの時間が足りないので、手がかりを手に入れていただければ幸いです。

ありがとう！マレパン

エディション後のコード：

public int partition(Comparable[] a, int left, int right) {
 // Partition a[left…right] such that

 // a[left…p-1] are all less than or equal to a[p]

 // and a[p+1…right] are all greater than or equal to

 // a[p]. Return p.

 Comparable pivot = a[left];
 int i = left +1;
 int j = right;
 while (i<=j){
     while (i<=j && a[i].compareTo(pivot) <= 0){
         i++;
     }
     while (i>=j && a[j].compareTo(pivot) >= 0){
         j--;
     }
     if (i<j){
     a[i] = a[j];
     }
 }
 if ( j != left){
 a[left] = a[j];
 a[j] = pivot;
 }

 return j;

}

4

4 に答える 4

2

の代わりにa < b、を記述しa.compareTo(b) < 0ます。

他の比較演算子も同様に記述されているため、

a[i] <= pivot

になります

a[i].compareTo(pivot) <= 0
于 2011-08-04T15:39:53.320 に答える
1

compareTo()代わりに、同等のメソッドを使用する必要があります。

だからa<bになりa.compareTo(b)<0ます。compareToメソッドは、aがbより小さい場合は<0、同じである場合は0、aがbより大きい場合は>0を返します。

Javaは演算子のオーバーロードをサポートしていないため、これが必要です。したがって、より小さい、より大きいなどの演算子は、ライブラリクラスやインターフェイスではなく、プリミティブ型（文字列などの一部の例外を除く）でのみ使用できます。

副次的な点として、これを学術目的だけでなく実際に使用している場合、Collections.sort()ほとんどの場合、使用は独自の実装よりも高速になります。

于 2011-08-04T15:40:39.783 に答える
1

私はあなたが書いたのと同じコードを使います

int comp = a[r].compareTo(pivot);
if (comp < 0) {
于 2011-08-04T15:41:24.733 に答える
1

これらはComparableオブジェクトであるため、<=..を使用することはできません。compareToメソッドを使用する必要があります。

while i <= j and ( a[i].compareTo(pivot) <= 0 )
于 2011-08-04T15:41:48.267 に答える