PHPの基本的なアルゴリズムは何ですか?

アルゴリズムはプログラムの核であるとよく言われますが、プログラムの良し悪しの鍵は、プログラムのアルゴリズムの質にあります。私はジュニア PHPer ですが、アルゴリズムに関することにはほとんど触れていません。ただし、バブル ソート、挿入ソート、選択ソート、クイック ソートの 4 つの基本アルゴリズムを習得する必要があると思います。

関連する推奨事項: 「PHP チュートリアル 」

要件: バブル ソート、クイック ソート、および選択ソートをそれぞれ使用します。挿入ソートメソッドは、以下の配列内の値を昇順にソートします。

$arr=array(11,3,56,62,21,66,32,78,36,76,39,88,34);

1. バブル ソート

はじめに:

バブル ソート (バブル ソート、台湾語訳: バブル ソートまたはバブル ソート) は、単純な並べ替えです。アルゴリズム。ソート対象のシーケンスを繰り返し調べて、2 つの要素を順番に比較し、順序が間違っている場合は入れ替えます。配列を訪問する作業は、それ以上の交換が必要なくなるまで繰り返されます。これは、配列がソートされたことを意味します。このアルゴリズムの名前は、小さい要素がスワッピングによって配列の先頭にゆっくりと「浮動」するという事実に由来しています。

ステップ:

1. 隣接する要素を比較します。最初のものが 2 番目のものより大きい場合は、両方を交換します。

2. 隣接する要素の各ペアに対して、最初の最初のペアから最後の最後のペアまで同じ作業を実行します。この時点では、最後の要素が最大の数値である必要があります。

3. 最後の要素を除くすべての要素に対して上記の手順を繰り返します。

4. 比較する数値のペアがなくなるまで、要素の数を減らしながら上記の手順を繰り返します。

特定のコード:

$arr=array(1,43,54,62,21,66,32,78,36,76,39);
function bubbleSort ($arr)
{
$len = count($arr);
//该层循环控制 需要冒泡的轮数
for ($i=1; $i<$len; $i++) {
//该层循环用来控制每轮 冒出一个数 需要比较的次数
for ($k=0; $k<$len-$i; $k++) {
if($arr[$k] > $arr[$k+1]) {
$tmp = $arr[$k+1]; // 声明一个临时变量
$arr[$k+1] = $arr[$k];
$arr[$k] = $tmp;
}
}
}
return $arr;
}

並べ替え効果:

2.並べ替えの選択

概要:

選択ソートは、シンプルで直感的なソート アルゴリズムです。仕組みは次のとおりです。まず、ソートされていないシーケンス内の最小の要素を見つけて、ソートされたシーケンスの先頭に格納します。次に、引き続きソートされていない残りの要素から最小の要素を見つけて、ソートされたシーケンスの最後に置きます。すべての要素がソートされるまで続きます。

具体的なコード:

//实现思路 双重循环完成，外层控制轮数，当前的最小值。内层 控制的比较次数
function select_sort($arr) {
//$i 当前最小值的位置， 需要参与比较的元素
for($i=0, $len=count($arr); $i<$len-1; $i++) {
//先假设最小的值的位置
$p = $i;
//$j 当前都需要和哪些元素比较，$i 后边的。
for($j=$i+1; $j<$len; $j++) {
//$arr[$p] 是 当前已知的最小值
if($arr[$p] > $arr[$j]) {
//比较，发现更小的,记录下最小值的位置；并且在下次比较时，应该采用已知的最小值进行比较。
$p = $j;
}
}
//已经确定了当前的最小值的位置，保存到$p中。
//如果发现 最小值的位置与当前假设的位置$i不同，则位置互换即可
if($p != $i) {
$tmp = $arr[$p];
$arr[$p] = $arr[$i];
$arr[$i] = $tmp;
}
}
//返回最终结果
return $arr;
}

ソート効果:

##3. 挿入ソート

はじめに:

挿入ソートのアルゴリズムの説明は、シンプルで直感的なソート アルゴリズムです。これは、順序付けされたシーケンスを構築することで機能し、並べ替えられていないデータの場合は、並べ替えられたシーケンス内で後ろから前にスキャンし、対応する位置を見つけて挿入します。挿入ソートの実装では、通常、インプレース ソート (つまり、O(1) 個の余分なスペースのみを使用するソート) が使用されるため、後ろから前へのスキャン プロセス中に、繰り返し、徐々にシフトする必要があります。要素を後方にソートし、最新の要素の挿入スペースを提供します。

手順:

1. 最初の要素から始めて、この要素はソートされたとみなすことができます

2. 次の要素を取り出して、ソートされた要素シーケンスを後ろから前にスキャンします。

3. (ソートされた) 要素が新しい要素より大きい場合は、要素を次の位置に移動します

#4並べ替えられた要素が新しい要素

#5 以下になる位置が見つかるまで、手順 3 を繰り返します。新しい要素を位置

#6 に挿入します。繰り返します。ステップ 2

特定のコード:

function insert_sort($arr)
{
$len=count($arr);
for($i=1; $i<$len; $i++) {
//获得当前需要比较的元素值。
$tmp = $arr[$i];
//内层循环控制 比较 并 插入
for($j=$i-1; $j>=0; $j--) {
//$arr[$i];//需要插入的元素; $arr[$j];//需要比较的元素
if($tmp < $arr[$j]) {
//发现插入的元素要小，交换位置
//将后边的元素与前面的元素互换
$arr[$j+1] = $arr[$j];
//将前面的数设置为 当前需要交换的数
$arr[$j] = $tmp;
} else {
//如果碰到不需要移动的元素
//由于是已经排序好是数组，则前面的就不需要再次比较了。
break;
}
}
}
//将这个元素 插入到已经排序好的序列内。
//返回
return $arr;
}

並べ替え効果:

4. クイック ソート

はじめに:

クイックソート Tony Hall が開発したソートアルゴリズムです。平均して、n 個の項目を並べ替えるには、O(n log n) 個の比較が必要です。最悪の場合、O(n2) 回の比較が必要になりますが、この状況は一般的ではありません。実際、クイックソートは、その内部ループがほとんどのアーキテクチャで効率的に実装でき、ほとんどの実世界のアプリケーションで適切に機能するため、他の Ο(n log n) アルゴリズムよりも大幅に高速であることがよくあります。必要な時間内に。

手順:

1. シーケンスから「ピボット」と呼ばれる要素を選択します。

2. シーケンスを並べ替えます (すべての要素)。基本値は基本値の前に配置され、基本値より大きい要素はすべて基本値の後ろに配置されます (同じ数値をどちらの側にも置くことができます)。このパーティションが終了すると、塩基はシーケンスの途中になります。これをパーティション操作と呼びます。

3. 基本値より小さい要素の部分配列と基本値より大きい要素の部分配列を再帰的に並べ替えます。

特定のコード:

function quick_sort($arr)
{
//判断参数是否是一个数组
if(!is_array($arr)) return false;
//递归出口:数组长度为1，直接返回数组
$length = count($arr);
if($length<=1) return $arr;
//数组元素有多个,则定义两个空数组
$left = $right = array();
//使用for循环进行遍历，把第一个元素当做比较的对象
for($i=1; $i<$length; $i++)
{
//判断当前元素的大小
if($arr[$i]<$arr[0]){
$left[]=$arr[$i];
}else{
$right[]=$arr[$i];
}
}
//递归调用
$left=quick_sort($left);
$right=quick_sort($right);
//将所有的结果合并
return array_merge($left,array($arr[0]),$right);
}

並べ替え効果:

以上がPHPの基本的なアルゴリズムは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。