PHPクイックソートクイックソート例の詳細な説明

この記事の例では、PHP クイック ソートについて説明します。参考のために皆さんと共有してください。詳細は次のとおりです:

クイックソート

クイックソートアルゴリズムでは、分割統治戦略が使用されます。まず、シーケンスが 2 つのサブシーケンスに分割され、シーケンス全体がソートされるまでサブシーケンスが再帰的にソートされます。 (つまり、2つに分割するという考え方です)

手順は次のとおりです:

シーケンス内のキー要素を軸として選択します

シーケンスを並べ替え、軸よりも小さい要素を前に移動します。軸よりも大きく、要素は軸の後ろに移動されます。分割後、軸は最終位置にあります。

は 2 つのサブシーケンス (小さい要素を持つサブシーケンスと大きい要素を持つサブシーケンス) を再帰的に並べ替えます。

たとえば、シーケンス $arr:

5 3 0 11 44​​ 7 23 2 最初の要素 $arr[0] = 5 を軸として設定し、フラグを low に設定します... トップは始まりを表し、 end
2 3 0 11 44​​ 7 23 2 の方向 (右) で比較を開始します: 22 3 0 11 44​​ 7 23 11 の方向で比較を開始します反対方向 (左) まで: 5low == top になるまで上記の手順を繰り返します 位置を軸要素 (5
2 3 0 5 44 7 23 11
) に置き換えますこのようにして、2 3 0 と 44 23 11 の 2 つの部分に分割できます
この方法で、開始ステップを再帰的に続行できます

アルゴリズムの実装:

class quick_sort{
    function quicksort(&$arr,$low,$top){
      if($low < $top){
        $pivotpos = $this->partition($arr,$low,$top);
        $this->quicksort($arr,$low,$pivotpos-1);
        $this->quicksort($arr,$pivotpos+1,$top);
      }
    }
    function partition(&$arr, $low ,$top){
      if($low == $top){
        return;
      }
  //   设置初始数值
      $com = $arr[$low];
      while($low!=$top){
  //      将比初始数值小的替换到左边
        while($top&&$top!=$low){
          if($com > $arr[$top]){
          $arr[$low++] = $arr[$top];
          break;
          }else{
            $top--;
          }
        }
  //      将比初始数值大的替换到右边
        while($low&&$low!=$top){
          if($com < $arr[$low]){
            $arr[$top--] = $arr[$low];
            break;
          }else{
            $low++;
          }
        }
      }
      $arr[$low] = $com;
      return $low;
    }
}

この記事が PHP プログラミングのすべての人に役立つことを願っています。

より詳細な PHP クイックソートの例と関連記事については、PHP 中国語 Web サイトに注目してください。