English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
この記事はPHPのクラスシックアルゴリズムの例をまとめました。皆さんに共有し、以下のように参照してください：
1、まず菱形を描いてみましょう。多くの人がCを学んだときに本に描かれているように、私たちはPHPで描いてみます。半分が終わりました。
考え方：何行ごとにforを回すか、その中でスペースと星印をforを回します。
<?php
for($i=0;$i<=3;$i++{
echo str_repeat(" ",3-$i);
echo str_repeat("*"$i*2+1);
echo $array[$i].' ';/echo '<br
}
2、バブルソート、Cでの基本的なアルゴリズム、小から大へと数の配列を並べ替えます。
考え方：この問題は小から大へと、最初のラウンドで一番小さいを並べ替え、次のラウンドで二番小さいを並べ替え、次のラウンドで三番小さいを並べ替え、以此類推……
<?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変更はありません。中間は前排の1つと左側の1行の和です。このアルゴリズムは、2次元配列で保存されます。また、1次元配列でも実現できます。一行ごとに表示されます。興味がある場合は、試してみてください。
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
}
}
//打印
for($i=0; $i<6; $i++{
for($j=0; $j<=$i; $j++) {
echo $a[$i][$j].' ';
}
echo $array[$i].' ';/echo '<br
}
4、在一组数中，要求插入一个数，按其原来顺序插入，维护原来排序方式。
思路：找到比要插入数大的那个位置，替换，然后把后面的数后移一位。
<?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、对一组数进行排序（快速排序算法）。
思路：通过一趟排序分成两部分，然后递归对这两部分排序，最后合并。
<?php
function q($array) {
function quick_sort($array){ 1) {return $array;}
//以$key为界，分成两个子数组
) return $array;
$l = array();
$r = array();
//分别进行递归排序，然后合成一个数组
$right_arr = array();1for ($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, $k);+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 $array[$i].' ';/echo '<br
$a = array_merge(range(1,4),range(1,4),range(1,4))；
print_r($a);
8、牛年求牛：一頭の母牛が、4歳で繁殖可能、毎年一头、生まれるのは全て同じ母牛で、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);
====================其他算法=========================
冒泡排序（bubble sort）— 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>';
print_r($d);
echo '</pre>';
}
插入排序（insertion sort）— 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>';print_r($d);echo '</pre>';
}
希尔排序（shell sort）— 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];
$left_arr[] = $array[$i];
break;
$arr[$j] = $tmp;
}
}
}
function dump( $d )
{
echo '<pre>';print_r($d);echo '</pre>';
}
快速排序（quicksort）— 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>';print_r($data);echo '</pre>';
}
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);
}
=================================================
バブルソート：数値を二つずつ交換し、最も小さい値が最も左側に配置されます。最も軽いバブルが一番上に配置されます。一列の数を二つずつ交換して、最も小さい数が最も左側に配置されます。各回で、残りの数の中で最も小さい数を得ることができます。'飛び出す'数は一つの並び替えられた範囲を構成し、残りの値は一つの無序範囲を構成し、並び替えられた範囲の各要素の値は無序範囲の各要素の値よりも小さいです。
クイックソート：基準値、左側と右側の二つの配列、再帰呼び出し、統合。
挿入ソート：ソート範囲を二分割し、左側が並び替えられ、右側が並び替えられない。右側から最初の要素を取り出し、左側に挿入します。この要素が左側の最も右側の要素よりも大きい場合、その場所に残ります。この要素が左側の最も右側の要素よりも小さい場合、最も右側の要素の元の位置に挿入し、最も右側の要素を一つ右に移動し、カウンタを減らし、前の要素と再び比較します。前の要素が挿入する要素よりも小さいまで繰り返します。これを繰り返します。
範囲の端点値の処理に注意し、配列の最初の要素のインデックスが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];
}
$left_arr[] = $array[$i];
{
$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;
}
/*
【バブルソート（一次元配列）】
【基本思想】：待排序データ要素の大小を比較し、2つのデータ要素の順序が逆の場合は交換を行い、逆序のデータ要素がいなくなるまで繰り返します。
【ソートプロセス】：ソートされる配列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]からデータ要素を1つ選択して比較の「基準」として使用します（Xと記します）、
この基準を使用して、現在の無序領域を左右の2つのより小さい無序領域に分割します：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［
1回目の交換後［27 38 65 97 76 13 49 49［
2回目の交換後［27 38 49 97 76 13 65 49［
Jを左にスキャンし、位置を変更しない、3回目の交換後［27 38 13 97 76 49 65 49［
Iを右にスキャンし、位置を変更しない、4回目の交換後［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){ 1if (count($array) <=
) return $array;
$key = $array[0];
$left_arr = array();
$right_arr = array();1for ($i=++{
; $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選択するソート方法に考慮すべき要素：
(2並べ替えられる要素の数n；
(3要素自体の情報量の大きさ；
(4キーの構造および分布状況；
2言語ツールの条件、補助空間の大きさなど。
(1)の要因： 5nが小さい場合(n<=
(2O(1)の時間複雑度を持つソート方法：直接挿入ソートまたは直接選択ソートを使用できます。直接挿入ソートでは、記録の移動操作が直接選択ソートよりも多く必要になるため、記録の情報量が大きい場合、直接選択ソートがより良いです。
(3ファイルの初期状態がキーで基本的に整列されている場合、直接挿入またはバブルソートを選択するのが適切です。2nが大きい場合、O(nlogn)の時間複雑度を持つソート方法：クイックソート、ヒープソート、またはマージソートを使用するべきです。
(4比較ソート方法を基に、各比較の後で二つの可能性しか発生しないため、比較判定プロセスを二分木で表現することができます。これにより、証明されます：ファイルのn個のキーがランダムに分布している場合、比較を利用するどんなソートアルゴリズムも少なくともO(nlogn)の時間複雑度を持つ排序方法：クイックソート、ヒープソート、またはマージソートが必要です。クイックソートは比較ベースの内部ソート法の中で最も優れているとされています。2n)的时间。
(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暗号化方法のまとめ》、《PHPエンコードとデコード操作の技術集》、《phpオブジェクト指向プログラムデザイン入門教程》、《PHP数学演算の技術集》、《PHP配列（Array）操作の技術集》、《php文字列（string）の使用法のまとめ》、《php正規表現の使用法のまとめ》、および《php一般的なデータベース操作の技術集》
希望本文が皆様のPHPプログラムデザインに役立つことを願っています。
声明：本文の内容はインターネットから取得しており、著作権者に帰属します。インターネットユーザーが自発的に貢献し、自己でアップロードしたものであり、本サイトは所有権を持ちません。また、人工編集は行われていません。著作権侵害を疑う内容がある場合は、以下のメールアドレスまでご連絡ください：notice#oldtoolbag.com（メールを送信する際、#を@に置き換えてください。申し訳ありませんが、関連する証拠を提供し、一旦確認が取れた場合、本サイトは即座に侵害疑いのコンテンツを削除します。）