本文實例總結了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 '<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 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、在一組數中,要求插入一個數,按其原來順序插入,維護原來排序方式。
思路:找到比要插入數大的那個位置,替換,然後把後面的數後移一位。
<?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歲可生育,每年一頭,所生均是一樣的母牛,到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]; else 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]; } 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加密方法總結》、《PHP編碼與轉碼操作技巧匯總》、《php面向對象程序設計入門教程》、《PHP數學運算技巧總結》、《PHP數組(Array)操作技巧大全》、《php字符串(string)用法總結》、《php正則表達式用法總結》、及《php常見數據庫操作技巧匯總》
希望本文所述對大家PHP程序設計有所幫助。