이 글은 주로 PHP 고전 알고리즘 모음을 소개하고, 다양한 공통 알고리즘 원리와 정렬, 검색, 순회, 연산 등의 구현 기술을 포함하여 다양한 공통 알고리즘을 정리했습니다. 도움이 필요한 친구들이 참고할 수 있습니다.
이 글은 예 PHP 클래식 알고리즘. 참고를 위해 모두와 공유합니다. 자세한 내용은 다음과 같습니다.
1. 먼저 재미삼아 마름모를 그려보겠습니다. 많은 사람들이 C를 배울 때 책에서 그렸습니다. PHP로 그려서 절반을 그려보겠습니다. .
아이디어: 한 번은 여러 줄에 대해 한 번, 그 다음에는 공백과 별표를 위해 한 번.
<?php for($i=0;$i<=3;$i++){ echo str_repeat(" ",3-$i); echo str_repeat("*",$i*2+1); 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이며, 가운데는 첫 번째 숫자와 왼쪽 행의 합이 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].' '; } 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. 숫자 집합을 정렬합니다(빠른 정렬 알고리즘).
아이디어: 한 번의 정렬을 통해 두 부분으로 나눈 다음 두 부분을 재귀적으로 정렬하고 최종적으로 병합합니다.
<?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 ''; }
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 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); }
=== === ==========================================
버블링 정렬: 값 교환 쌍으로, 맨 왼쪽에 가장 작은 값이 있고 맨 위에 있는 가장 가벼운 거품과 같습니다. 전체 숫자 열을 가장 왼쪽에 있는 숫자로 한 번 교환합니다. 매번 남은 숫자 중에서 가장 작은 숫자를 얻을 수 있습니다. "팝업된" 숫자는 순서화된 간격을 형성하고 나머지 값은 An을 형성합니다. 순서가 없는 간격이고, 순서가 있는 간격의 각 요소 값은 순서가 없는 간격의 값보다 작습니다.
빠른 정렬: 기본 번호, 왼쪽 및 오른쪽 배열, 재귀 호출, 병합.
삽입 정렬: 정렬 간격이 두 부분으로 나누어져 왼쪽은 순서가 지정되고 오른쪽은 순서가 지정되지 않습니다. 오른쪽 간격에서 첫 번째 요소를 가져와서 이 요소가 가장 오른쪽 간격보다 큰 경우 왼쪽 간격에 삽입합니다. 왼쪽 간격의 요소는 그대로 둡니다. 이 요소가 왼쪽 범위의 가장 오른쪽 요소보다 작으면 가장 오른쪽 요소의 원래 위치에 삽입됩니다. 한 위치 오른쪽으로 이동하면 계산기가 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!