PHP クラシックアルゴリズムのコレクション-PHPチュートリアル-php.cn

この記事の例は、PHP の古典的なアルゴリズムをまとめたものです。参考として皆さんと共有してください。詳細は次のとおりです。

1. まず、多くの人が C を学習していたときに本で描いたことがあります。それを PHP で描いてみましょう。。

アイデア: 行数ごとに 1 回、その後、内部のスペースとアスタリスクに対して 1 回。

<?php
for($i=0;$i<=3;$i++){
  echo str_repeat(" ",3-$i);
  echo str_repeat("*",$i*2+1);
  echo &#39;<br/>&#39;;
}

ログイン後にコピー

2. C の基本アルゴリズムであるバブルソートは、一連の数値を小さいものから大きいものへと並べ替えます。

思考: この質問は、小さいものから大きいものへとランク付けされます。最初のラウンドが最も小さく、2 番目のラウンドが 2 番目に小さく、3 番目のラウンドが 3 番目に小さいというようになります...

<?php
$arr = array(1,3,5,32,756,2,6);
$len = count($arr);
for ($i=0;$i<$len-1;$i++){
  for ($j=$i+1;$j<$len;$j++){
    if($arr[$i]>$arr[$j]){//从小到大
      $p = $arr[$i];
      $arr[$i] = $arr[$j];
      $arr[$j]= $p;
    }
  }
}
var_dump($arr);

ログイン後にコピー

3ヤン・フイ・トライアングル、PHP書き込みを使用。

アイデア: 各行の最初と最後の桁は 1 で、中央は最初の桁と左の行の合計です。このアルゴリズムは 2 次元配列に保存されます。次元配列を使用する実装も可能で、出力は行ごとに行われます。興味がある場合は、それを書いて遊んでみてください。

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

<?php
//每行的第一个和最后一个都为1，写了6行
 for($i=0; $i<6; $i++) {
  $a[$i][0]=1;
  $a[$i][$i]=1;
 }
//出除了第一位和最后一位的值，保存在数组中
 for($i=2; $i<6; $i++) {
  for($j=1; $j<$i; $j++) {
   $a[$i][$j] = $a[$i-1][$j-1]+$a[$i-1][$j];
  }
 }
//打印
 for($i=0; $i<6; $i++){
  for($j=0; $j<=$i; $j++) {
  echo $a[$i][$j].&#39; &#39;;
  }
  echo &#39;<br/>&#39;;
 }

ログイン後にコピー

4. 数字のセットに数字を挿入したい場合。、元の順序で [挿入] を押し、元の並べ替え方法を維持します。

アイデア: 挿入する数値より大きい位置を見つけて置き換え、次の数値を 1 つ戻します。

<?php
$in = 2;
$arr = array(1,1,1,3,5,7);
$n = count($arr);
//如果要插入的数已经最大，直接打印
if($arr[$n-1] < $in) {
  $arr[$n+1] = $in; print_r($arr);
  }
for($i=0; $i<$n; $i++) {
//找出要插入的位置
  if($arr[$i] >= $in){
    $t1= $arr[$i];
    $arr[$i] = $in;
//把后面的数据后移一位
    for($j=$i+1; $j<$n+1; $j++) {
      $t2 = $arr[$j];
      $arr[$j] = $t1;
      $t1 = $t2;
  }
//打印
  print_r($arr);
  die;
  }
}

ログイン後にコピー

5. 一連の数値を並べ替えます (クイック並べ替えアルゴリズム)。

アイデア: 1 回の並べ替えで 2 つの部分に分割し、次に 2 つの部分を再帰的に並べ替えて、最後に結合します。

<?php
function q($array) {
  if (count($array) <= 1) {return $array;}
//以$key为界，分成两个子数组
  $key = $array[0];
  $l = array();
  $r = array();
//分别进行递归排序，然后合成一个数组
  for ($i=1; $i<count($array); $i++) {
  if ($array[$i] <= $key) { $l[] = $array[$i]; }
  else { $r[] = $array[$i]; }
 }
  $l = q($l);
  $r = q($r);
  return array_merge($l, array($key), $r);
}
$arr = array(1,2,44,3,4,33);
print_r( q($arr) );

ログイン後にコピー

6. 配列内で必要な要素を見つけます (二分探索アルゴリズム)。

アイデア: 配列内の特定の値を境界として使用し、最後まで再帰的に検索します。

<?php
function find($array, $low, $high, $k){
  if ($low <= $high){
  $mid = intval(($low+$high)/2);
    if ($array[$mid] == $k){
    return $mid;
  }elseif ($k < $array[$mid]){
    return find($array, $low, $mid-1, $k);
    }else{
    return find($array, $mid+1, $high, $k);
    }
  }
  die(&#39;Not have...&#39;);
}
//test
$array = array(2,4,3,5);
$n = count($array);
$r = find($array,0,$n,5)

ログイン後にコピー

7. array_merge() を使用せずに複数の配列を結合する質問はフォーラムからのものです。

アイデア: 各配列を走査し、新しい配列を再形成します。質問 n年後には何頭の牛が生まれるでしょうか？

<?php
function t(){
  $c = func_num_args()-1;
  $a = func_get_args();
  //print_r($a);
  for($i=0; $i<=$c; $i++){
    if(is_array($a[$i])){
      for($j=0; $j<count($a[$i]); $j++){
        $r[] = $a[$i][$j];
      }
    } else {
      die(&#39;Not a array!&#39;);
    }
  }
  return $r;
}
//test
print_r(t(range(1,4),range(1,4),range(1,4)));
echo &#39;<br/>&#39;;
$a = array_merge(range(1,4),range(1,4),range(1,4));
print_r($a);

ログイン後にコピー

==================== その他のアルゴリズム===================== = ====

バブルソート (バブルソート) — O(n2)

<?php
function t($n) {
    static $num = 1
    for($j=1; $j<=$n; $j++){
        if($j>=4 && $j<15) {$num++;t($n-$j);}
        if($j==20){$num--;}
     }
     return $num;
}
//test
echo t(8);

ログイン後にコピー

挿入ソート (挿入ソート) — O(n2)

$data = array(3,5,9,32,2,1,2,1,8,5);
dump($data);
BubbleSort($data);
dump($data);
function BubbleSort(& $arr)
{
$limit = count($arr);
for($i=1; $i<$limit; $i++)
{
  for($p=$limit-1; $p>=$i; $p--)
  {
  if($arr[$p-1] > $arr[$p])
  {
   $temp = $arr[$p-1];
   $arr[$p-1] = $arr[$p];
   $arr[$p] = $temp;
  }
  }
}
}
function dump( $d )
{
echo &#39;<pre class="brush:php;toolbar:false">&#39;;
print_r($d);
echo &#39;

'; }

ログイン後にコピー

ヒルソート (シェルソート) — O(n log n)

$data = array(6,13,21,99,18,2,25,33,19,84);
$nums = count($data)-1;
dump( $data );
InsertionSort($data,$nums);
dump( $data );
function InsertionSort(& $arr,$n )
{
for( $i=1; $i<=$n; $i++ )
{
  $tmp = $arr[$i];
  for( $j = $i; $j>0 && $arr[$j-1]>$tmp; $j-- )
  {
  $arr[$j] = $arr[$j-1];
  }
  $arr[$j] = $tmp;
}
}
function dump( $d )
{
echo &#39;<pre class="brush:php;toolbar:false">&#39;;print_r($d);echo &#39;

'; }

ログイン後にコピー

クイックソート (クイックソート) — O(n log n)

$data = array(6,13,21,99,18,2,25,33,19,84);
$nums = count($data);
dump( $data );
ShellSort($data,$nums);
dump( $data );
function ShellSort(& $arr,$n )
{
for( $increment = intval($n/2); $increment > 0; $increment = intval($increment/2) )
{
  for( $i=$increment; $i<$n; $i++ )
  {
  $tmp = $arr[$i];
  for( $j = $i; $j>= $increment; $j -= $increment )
   if( $tmp < $arr[ $j-$increment ] )
   $arr[$j] = $arr[$j-$increment];
   else
   break;
  $arr[$j] = $tmp;
  }
}
}
function dump( $d )
{
echo &#39;<pre class="brush:php;toolbar:false">&#39;;print_r($d);echo &#39;

'; }

ログイン後にコピー

================== ================================

バブルソート: 値をペアで交換し、最も小さい値を並べ替えます。左は最も軽い泡が上にあるようなものです。数値の列全体を 1 回交換し、そのたびに残りの数値の中で最も小さい数値を取得し、順序付けられた間隔を形成し、残りの値を An とします。順序付けされていない間隔であり、順序付けされた間隔の各要素の値は順序付けされていない間隔の値よりも小さくなります。

クイックソート: 基数、左右の配列、再帰呼び出し、マージ。

挿入ソート: ソート間隔は 2 つの部分に分割され、左側は順序付けされ、右側は順序付けされていません。右側の間隔から最初の要素を取得し、この要素が右端の間隔よりも大きい場合は、それを左側の間隔に挿入します。この要素が左の範囲の右端の要素より小さい場合は、右端の要素の元の位置に挿入されます。 1 つ右に移動すると、計算機は 1 つ減り、前の要素が挿入する要素より小さくなるまで再び前の要素と比較され、上記の手順を繰り返します。

区間のエンドポイント値の処理に注目してください。配列の最初の要素の添え字は0です。

$data = array(6,13,21,99,18,2,25,33,19,84);
dump($data);
quicks($data,0,count($data)-1);
dump($data);
function dump( $data){
echo &#39;<pre class="brush:php;toolbar:false">&#39;;print_r($data);echo &#39;

'; } function QuickSort(& $arr,$left,$right) { $l = $left; $r = $right; $pivot = intval(($r+$l)/2); $p = $arr[$pivot]; do { while(($arr[$l] < $p) && ($l < $right)) $l++; while(($arr[$r] > $p) && ($r > $left)) $r--; if($l <= $r) { $temp = $arr[$l]; $arr[$l] = $arr[$r]; $arr[$r] = $temp; $l++; $r--; } } while($l <= $r); if($left < $r) QuickSort(&$arr,$left,$r); if($l < $right) QuickSort(&$arr,$l,$right); }

ログイン後にコピー

============== ========= =================

<?php
//PHP常用排序算法
function bubblesort ($array)
{
$n = count ($array);
for ($i = 0; $i < $n; $i++)
{
for ($j = $n - 2; $j >= $i; $j--) //[0,i-1] [i,n-1]
{
if ($array[$j] > $array[$j + 1])
{
$temp = $array[$j];
$array[$j] = $array[$j + 1];
$array [$j + 1] = $temp;
}
}
}
return $array;
}
$array = array (3,6,1,5,9,0,4,6,11);
print_r (bubblesort ($array));
echo &#39;<hr>&#39;;
function quicksort ($array)
{
$n = count ($array);
if ($n <= 1)
{
return $array;
}
$key = $array[&#39;0&#39;];
$array_r = array ();
$array_l = array ();
for ($i = 1; $i < $n; $i++)
{
if ($array[$i] > $key)
{
$array_r[] = $array[$i];
}
else
{
$array_l[] = $array[$i];
}
}
$array_r = quicksort ($array_r);
$array_l = quicksort ($array_l);
$array = array_merge ($array_l, array($key), $array_r);
return $array;
}
print_r (quicksort ($array));
echo &#39;<hr>&#39;;
function insertsort ($array)
{
$n = count ($array);
for ($i = 1; $i < $n; $i++) //[0,i-1] [i,n]
{
$j = $i - 1;
$temp = $array[$i];
while ($array[$j] > $temp)
{
$array[$j + 1] = $array[$j];
$array[$j] = $temp;
$j--;
}
}
return $array;
}
print_r (insertsort ($array));
?>

ログイン後にコピー

<?php
/*
【插 入排序（一维数组）】
【基本思想】：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素 全部插入完为止。
【示例】：
[初始关键字] [49] 38 65 97 76 13 27 49
J=2(38) [38 49] 65 97 76 13 27 49
J=3(65) [38 49 65] 97 76 13 27 49
J=4(97) [38 49 65 97] 76 13 27 49
J=5(76) [38 49 65 76 97] 13 27 49
J=6(13) [13 38 49 65 76 97] 27 49
J=7(27) [13 27 38 49 65 76 97] 49
J=8(49) [13 27 38 49 49 65 76 97]
*/
function insert_sort($arr){
$count = count($arr);
for($i=1; $i<$count; $i++){
  $tmp = $arr[$i];
  $j = $i - 1;
  while($arr[$j] > $tmp){
   $arr[$j+1] = $arr[$j];
   $arr[$j] = $tmp;
   $j--;
  }
}
return $arr;
}
/*
【选择排序（一维数组）】
【基 本思想】：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
【示例】：
[初 始关键字] [49 38 65 97 76 13 27 49]
第一趟排序后 13 ［38 65 97 76 49 27 49]
第 二趟排序后 13 27 ［65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第 四趟排序后 13 27 38 49 [49 97 65 76]
第五趟排序后 13 27 38 49 49 [97 97 76]
第 六趟排序后 13 27 38 49 49 76 [76 97]
第七趟排序后 13 27 38 49 49 76 76 [ 97]
最 后排序结果 13 27 38 49 49 76 76 97
*/
function select_sort($arr){
$count = count($arr);
for($i=0; $i<$count; $i++){
  $k = $i;
  for($j=$i+1; $j<$count; $j++){
    if ($arr[$k] > $arr[$j])
      $k = $j;
}
  if($k != $i){
    $tmp = $arr[$i];
    $arr[$i] = $arr[$k];
    $arr[$k] = $tmp;
  }
}
return $arr;
}
/*
【冒泡排序（一维数组） 】
【基本思想】：两两比较待排序数据元素的大小，发现两个数据元素的次序 相反时即进行交换，直到没有反序的数据元素为止。
【排序过程】：设想被排序的数组R［1..N］垂直竖立，将每个数据元素看作有重量的气泡，根据 轻气泡不能在重气泡之下的原则，
从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是 轻者在上，重者在下为止。
【示例】：
49 13 13 13 13 13 13 13
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49 49 49 49 49
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49 49 49 76 97 97 97 97
*/
function bubble_sort($array){
$count = count($array);
if ($count <= 0) return false;
for($i=0; $i<$count; $i++){
  for($j=$count-1; $j>$i; $j--){
   if ($array[$j] < $array[$j-1]){
    $tmp = $array[$j];
    $array[$j] = $array[$j-1];
    $array[$j-1] = $tmp;
   }
  }
}
return $array;
}
/*
【快速排序（一 维数组）】
【基本思想】：在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，
用此基准将当前无序区划分为 左右两个较小的无序区：R[1..I-1]和R[I 1..H]，且左边的无序子区中数据元素均小于等于基准元素，
右边的无序子区中数据元素均大 于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I 1..H](1≤I≤H)，
当R[1..I-1] 和R[I 1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。
【示例】：
初始关键字 [49 38 65 97 76 13 27 49］
第一次交换后 ［27 38 65 97 76 13 49 49］
第二次交换后 ［27 38 49 97 76 13 65 49］
J向左扫描，位置不变，第三次交换后 ［27 38 13 97 76 49 65 49］
I向右扫描，位置不变，第四次交换后 ［27 38 13 49 76 97 65 49］
J向左扫描 ［27 38 13 49 76 97 65 49］
（一次划分过程）
初始关键字 ［49 38 65 97 76 13 27 49］
一趟排序之后 ［27 38 13］ 49 ［76 97 65 49］
二趟排序之后 ［13］ 27 ［38］ 49 ［49 65］76 ［97］
三趟排序之后 13 27 38 49 49 ［65］76 97
最后的排序结果 13 27 38 49 49 65 76 97
各趟排序之后的状态
*/
function quick_sort($array){
if (count($array) <= 1) return $array;
$key = $array[0];
$left_arr = array();
$right_arr = array();
for ($i=1; $i<count($array); $i++){
  if ($array[$i] <= $key)
   $left_arr[] = $array[$i];
  else
   $right_arr[] = $array[$i];
}
$left_arr = quick_sort($left_arr);
$right_arr = quick_sort($right_arr);
return array_merge($left_arr, array($key), $right_arr);
}
/*打印数组全部内容*/
function display_arr($array){
$len = count($array);
for($i = 0; $i<$len; $i++){
  echo $array[$i].&#39; &#39;;
}
echo &#39;<br />&#39;;
}
/*
几种排序算法的比较和选择
1. 选取排序方法需要考虑的因素：
(1) 待排序的元素数目n；
(2) 元素本身信息量的大小；
(3) 关键字的结构及其分布情况；
(4) 语言工具的条件，辅助空间的大小等。
2. 小结：
(1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较 好。
(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
(3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序法中被认为是最好的方法。
(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关 键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlog2n)的时间。
(5) 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。
*/
/*排序测试*/
$a = array(&#39;12&#39;,&#39;4&#39;,&#39;16&#39;,&#39;8&#39;,&#39;13&#39;,&#39;20&#39;,&#39;5&#39;,&#39;32&#39;);
echo &#39;The result of insert sort:&#39;;
$insert_a = insert_sort($a);
display_arr($insert_a);
echo &#39;The result of select sort:&#39;;
$select_a = select_sort($a);
display_arr($select_a);
echo &#39;The result of bubble sort:&#39;;
$bubble_a = bubble_sort($a);
display_arr($bubble_a);
echo &#39;The result of bubble sort:&#39;;
$quick_a = quick_sort($a);
display_arr($quick_a);
?>

ログイン後にコピー

この記事が PHP プログラミングの皆様のお役に立てれば幸いです。

PHP クラシックアルゴリズムコレクションに関連するその他の記事については、PHP 中国語 Web サイトに注目してください。