1

特定の入力配列をソートするように見えるが、完全にはソートされていないように見えるこのQuickSortアルゴリズムがあります。

public static int partition(int[] A,int low,int high){
    int pivot=A[high-1];
    int i=low-1;
    int temp=0;
    for(int j=low;j<A.length-1;j++){
        if(A[j]<pivot){
            i++;
            temp = A[j];
            A[j]=A[i];
            A[i]=temp;
        }
    }
    temp=A[high-1];
    A[high-1]=A[i+1];
    A[i+1]=temp;
    return i+1;
}

public static void Qsort(int[] A,int low,int high){
    if(low<high){
        int p=partition(A,low,high);
        Qsort(A,low,p-1);
        Qsort(A,p+1,high);
      }
}

私はそのようにメインでメソッドQsortを呼び出しています

Qsort(arr,0,arr.length);

たとえば、この配列は正しくソートされています

6,5,3,7,1,2

しかし、これは

{6,5,3,7,1,2,4} is sorted like this {1 3 2 4 5 6 7}

最後のインデックスを 4 ではなく 8 に変更すると、機能します。ややこしい。エラーは軽微だと思いますが、見つかりません。

助けてくれてありがとう。

編集済み: 問題の正しい解決策:

public static int partition(int[] A,int low,int high){
   int pivot=A[high];
   int i=low;
   int temp=0;
   for(int j=low;j<high;j++){
      if(A[j]<pivot){
         temp = A[j];
         A[j]=A[i];
         A[i]=temp;
         i++;
      }
  }
  temp=A[high];
  A[high]=A[i];
  A[i]=temp;
  return i;
}

メインの Qsort への呼び出しは次のようになります:(重要でした)

Qsort(arr,0,arr.length-1);

助けてくれてありがとう。

4

1 に答える 1

0 
public static int partition(int[] A,int low,int high){
    int pivotIndex=0;
    int pivot=A[pivotIndex];
    int i=low;    
    int temp=A[pivotIndex];
    A[pivotIndex]=A[high];
    A[high]=temp;
    for(int j=low;j<high;j++){
        if(A[j]<pivot){
            temp = A[j];
            A[j]=A[i];
            A[i]=temp;
            i++;
        }
    }
    temp=A[high-1];
    A[high-1]=A[i+1];
    A[i+1]=temp;
    return i;
}

機能させるために必要ないくつかの改善があります。

  1. -1 ほど高くないピボット インデックスを選択します。簡単にするために、0 を使用します。
  2. for ループに入る前に要素の pivotIndex を high に交換する
  3. スワップ前ではなく、スワップ後に storeIndex i を増やします
  4. i++ の代わりに storeIndex i を返します
于 2013-10-27T20:39:10.007 に答える