PHPクイックソートの原理、実装方法、事例分析-PHPチュートリアル-php.cn

PHPクイックソートの原理、実装方法、事例分析

墨辰丷

リリース： 2023-03-29 12:06:02

オリジナル

1369 人が閲覧しました

この記事では主にPHPクイックソートの原理と実装方法を紹介し、サンプルの形でPHPクイックソートのアルゴリズム原理と具体的な実装テクニックを分析します。

<?php
$n = array(&#39;13&#39;,&#39;14&#39;,&#39;55&#39;,&#39;10&#39;,&#39;54&#39;,&#39;2&#39;,&#39;79&#39;,&#39;106&#39;,&#39;89&#39;,&#39;90&#39;,&#39;22&#39;,&#39;60&#39;,&#39;111&#39;,&#39;77777&#39;,&#39;-110&#39;,&#39;-10&#39;,&#39;123&#39;);
function partition($n,$left,$right)
{
  global $n;
  $pivot = $n[$left];
  $lo=$left;
  $hi=$right+1;
  while($lo+1!=$hi) {
    if($n[$lo+1]<$pivot)
      $lo++;
    else if($n[$hi-1]>$pivot)
      $hi--;
    else{
      $t=$n[$lo+1];
      $n[$lo+1]=$n[$hi-1];
      $n[$hi-1]=$t;
      $lo++;
      $hi--;
    }
  }
  $n[$left]=$n[$lo];
  $n[$lo]=$pivot;
  return $lo;
}
function quicksort($n,$left,$right)
{
  global $n;
  $dp = 0;
  if ($left<$right) {
     $dp=partition($n,$left,$right);
     quicksort($n,$left,$dp-1);
     quicksort($n,$dp+1,$right);
  }
}
quicksort($n,0,sizeof($n)-1);
print_r($n);
?>

ログイン後にコピー

クイックソートは、バブルソートを改良したアンチリスクアルゴリズムです。その基本的な考え方は、一方向の並べ替えによって並べ替えられるデータを 2 つの独立した部分に分割し、一方の部分のすべてのデータがもう一方の部分のすべてのデータよりも小さくなり、データの 2 つの部分が順番に並べ替えられることです。迅速に並べ替えるために、並べ替えプロセス全体を再帰的に実行して、データ全体が順序付けられたシーケンスになるようにすることができます。

ソートする配列がA[1]...A[N]であるとすると、まず任意のデータ（通常は最初のデータ）をキーデータとして選択し、それより小さいすべての数値をその前に置きます。それより大きい数字がその後ろに置かれるこのプロセスは、1 桁クイックソートと呼ばれます。クイックソートのアルゴリズムは次のとおりです:

1) 2 つの変数 I と J を設定します。ソートが開始されると、I:=1、J:=N になります。

2) 最初の配列要素をキーデータとして使用し、値を Give X に割り当てます。、つまり交換

4)、I から後方に検索、つまり前から後ろに検索 (I: =I+1)、X より大きい最初の値を見つけ、2 つを交換します

5)、ステップを繰り返します。 I=J まで 3、4 ステップ。

クイックソートはこのプロセスを再帰的に呼び出します。このデータシーケンスを 49 を中間点として分割し、前部分と後部分でそれぞれ同様のクイックソートを実行します。これにより、高速ソートが完了します。データシーケンス全体のソートソートし、最後にこのデータシーケンスを順序付けられたシーケンスに変換します

概要: 上記がこの記事の全内容です。皆さんの学習に役立つことを願っています。