ホームページ >バックエンド開発 >PHPチュートリアル >PHP のクラシック アルゴリズムのコレクション
PHP のクラシック アルゴリズムのコレクション
- 不言オリジナル
- 2018-04-14 11:38:171434ブラウズ
この記事では、主に PHP の古典的なアルゴリズムのコレクションを紹介し、ソート、検索、トラバーサル、操作などのさまざまな一般的なアルゴリズムの原則と実装テクニックを含めて、さまざまな一般的なアルゴリズムをまとめています。 PHP クラシック アルゴリズムの例。参考までに、詳細は以下の通りです:
1. まず、C を学習していたときに本でひし形を描いてみましょう。それ。
アイデア: 行数ごとに 1 回、その後、内部のスペースとアスタリスクに対して 1 回。
<?php
for($i=0;$i<=3;$i++){
echo str_repeat(" ",3-$i);
echo str_repeat("*",$i*2+1);
echo '<br/>';
}
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. Yang Hui Triangle、PHP で書かれています。
アイデア: 各行の最初と最後の桁は 1 で、中央は最初の桁と左の行の合計です。このアルゴリズムは 2 次元配列に保存されます。次元配列を使用する実装も可能で、出力は行ごとに行われます。興味がある場合は、それを書いて遊んでみてください。
1
1 11 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].' ';
}
echo '<br/>';
}
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('Not have...');
}
//test
$array = array(2,4,3,5);
$n = count($array);
$r = find($array,0,$n,5)
7. array_merge() を使用せずに複数の配列を結合する 質問はフォーラムからのものです。
アイデア: 各配列を走査し、新しい配列を再形成します。
<?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('Not a array!');
}
}
return $r;
}
//test
print_r(t(range(1,4),range(1,4),range(1,4)));
echo '<br/>';
$a = array_merge(range(1,4),range(1,4),range(1,4));
print_r($a);
8. 牛年に牛を頼む: 4歳で子供を産む牛がいて、毎年1頭ずつ産まれますが、その子孫はすべて同じです牛は 15 歳で不妊手術を受け、子供を産むことができなくなり、20 歳で亡くなります。n 年後には何頭の牛がいるか尋ねてください。 (フォーラムより)
<?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 '<pre class="brush:php;toolbar:false">';
print_r($d);
echo '';
}
挿入ソート — O(n2)
$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 '<pre class="brush:php;toolbar:false">';print_r($d);echo '';
}
ヒルソート (シェルソート) — 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 '<pre class="brush:php;toolbar:false">';print_r($d);echo '';
}
クイックソート (クイックソート) — O(n log n)
$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 '<pre class="brush:php;toolbar:false">';print_r($data);echo '';
}
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);
}
=== === ===========================================
バブリング並べ替え: 値を入れ替えるペアで、一番上の最も軽いバブルと同じように、最も小さい値が左端にあります。数値の列全体を 1 回交換し、そのたびに残りの数値の中で最も小さい数値を取得し、順序付けられた間隔を形成し、残りの値を An とします。順序付けされていない間隔であり、順序付けされた間隔の各要素の値は順序付けされていない間隔の値よりも小さくなります。
クイックソート: 基数、左右の配列、再帰呼び出し、マージ。
挿入ソート: ソート間隔は 2 つの部分に分割され、左側は順序付けされ、右側は順序付けされていません。右側の間隔から最初の要素を取得し、この要素が右端の間隔よりも大きい場合は、それを左側の間隔に挿入します。この要素が左の範囲の右端の要素より小さい場合は、右端の要素の元の位置に挿入されます。 1 つ右に移動すると、計算機は 1 つ減り、前の要素が挿入する要素より小さくなるまで再び前の要素と比較され、上記の手順を繰り返します。
間隔のエンドポイント値の処理に注意してください。配列の最初の要素の添え字は 0 です。
<?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 '<hr>';
function quicksort ($array)
{
$n = count ($array);
if ($n <= 1)
{
return $array;
}
$key = $array['0'];
$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 '<hr>';
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].' ';
}
echo '<br />';
}
/*
几种排序算法的比较和选择
1. 选取排序方法需要考虑的因素：
(1) 待排序的元素数目n；
(2) 元素本身信息量的大小；
(3) 关键字的结构及其分布情况；
(4) 语言工具的条件，辅助空间的大小等。
2. 小结：
(1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较 好。
(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
(3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序法中被认为是最好的方法。
(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关 键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlog2n)的时间。
(5) 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。
*/
/*排序测试*/
$a = array('12','4','16','8','13','20','5','32');
echo 'The result of insert sort:';
$insert_a = insert_sort($a);
display_arr($insert_a);
echo 'The result of select sort:';
$select_a = select_sort($a);
display_arr($select_a);
echo 'The result of bubble sort:';
$bubble_a = bubble_sort($a);
display_arr($bubble_a);
echo 'The result of bubble sort:';
$quick_a = quick_sort($a);
display_arr($quick_a);
?>/**
* 排列组合
* 采用二进制方法进行组合的选择，如表示5选3时，只需有3位为1就可以了，所以可得到的组合是 01101 11100 00111 10011 01110等10种组合
*
* @param 需要排列的数组 $arr
* @param 最小个数 $min_size
* @return 满足条件的新数组组合
*/
function pl($arr,$size=5) {
$len = count($arr);
$max = pow(2,$len);
$min = pow(2,$size)-1;
$r_arr = array();
for ($i=$min; $i<$max; $i++){
$count = 0;
$t_arr = array();
for ($j=0; $j<$len; $j++){
$a = pow(2, $j);
$t = $i&$a;
if($t == $a){
$t_arr[] = $arr[$j];
$count++;
}
}
if($count == $size){
$r_arr[] = $t_arr;
}
}
return $r_arr;
}
$pl = pl(array(1,2,3,4,5,6,7),5);
var_dump($pl);
//递归算法
//阶乘
function f($n){
if($n == 1 || $n == 0){
return 1;
}else{
return $n*f($n-1);
}
}
echo f(5);
//遍历目录
function iteral($path){
$filearr = array();
foreach (glob($path.'\*') as $file){
if(is_dir($file)){
$filearr = array_merge($filearr,iteral($file));
}else{
$filearr[] = $file;
}
}
return $filearr;
}
var_dump(iteral('d:\www\test'));関連する推奨事項:
phpの古典的なアルゴリズムの例分析橋を渡るPHPクラシックアルゴリズム以上がPHP のクラシック アルゴリズムのコレクションの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
声明：
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。