0

私は配列リストのクイックソートを書きましたが、現状ではロジックは健全なようです。私が抱えている問題は、要素の交換にあります。起こっているように見えるのは、要素を交換するのではなく、メソッドが既存の要素を交換する要素に置き換えていることです。実行例は [幸せ、りんご、食べる、食べ物] のようなリストから始まり、並べ替えが実行されると [幸せ、幸せ、幸せ、食べ物] になります。私の間違いは単純だと確信していますが、あまりにも長い間それを見つめていたので、新しい目が必要です. これまでの私のコードは次のとおりです。前もって感謝します!

String pivot = list.get(0); // Choose the first element as the pivot
      int low = first + 1; // Index for forward search
      int high = last; // Index for backward search

      while (high > low) 
      { // Search forward from left
          while (low <= high && list.get(low).compareTo(pivot) <= 0)
          {

              low++;
          }
      // Search backward from right
      while (low <= high && list.get(high).compareTo(pivot) > 0)
      {
          high--;
      }
      // Swap two elements in the list
      if (high > low) 
      {

          String temp = list.get(high);
          list.set(high,list.get(low));
          list.set(low,temp);

      }
    }
    while (high > first && list.get(high).compareTo(pivot) <= 0)
    {

        high--;
    }
    // Swap pivot with list[high]
    if (list.get(high).compareTo(pivot) < 0) 
    { 
        list.set(first, list.get(high));
        list.set(high,pivot);
        return high;
    }
    else 
    {
        return first;
    }
  }
4

2 に答える 2

0

はい、間違いは簡単だと思います。これを試して

String tempHigh = list.get(high);
String tempLow = list.get(low);
list.set(high, tempLow);
list.set(low, tempHigh);

Javaでは、割り当ては参照を通じて行われるためです。コードでは、高い値と低い位置の両方に高い値を設定するだけです。ピボットを list[high] に交換すると、同じことが起こります

于 2013-04-30T03:14:28.827 に答える
0

問題(使用するピボット選択を修正した後list.get(first))は

while (high > first && list.get(high).compareTo(pivot) <= 0)

その時点で、インデックスの前 (およびインデックスを含む) のすべての要素highは、(辞書編集的に) ピボットより小さいか、または等しくなります。したがって

while (high > first && list.get(high).compareTo(pivot) <= 0) {

    high--;
}

と省略できますhigh = first

これは、最初の要素と

String pivot = list.get(0);

あなたの例ではインデックス0の要素が最大であるため、ピボット選択。

if (list.get(high).compareTo(pivot) < 0) 
{ 
    list.set(first, list.get(high));
    list.set(high,pivot);
    return high;
}

ブランチが取得され、のlist.set(first, list.get(high));ため何もせず、ピボットをインデックス にコピーしhigh == firstます。list.set(high,pivot);high (== first)

問題のある行で必要なのは

if (list.get(high).compareTo(pivot) > 0) {
    --high;
}

最初のパーティショニング ループの後、index の要素highがピボットより大きい場合、前の要素はピボット以下になります。それ以外の場合highは、ピボットより大きくない要素の最大インデックスです。

于 2013-04-30T04:14:25.563 に答える