English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
This article summarizes the classic algorithms of PHP. Shared for everyone's reference, as follows:
1, let's draw a diamond for fun, many people have drawn it in books when learning C, let's draw it with PHP, half of it is done.
Thought: How many lines to loop for, and then loop for spaces and asterisks inside.
<?php
for($i=0;$i<=3;$i++{
echo str_repeat(" ",3-$i);
echo str_repeat("*"$i*2+1
echo '<br/>';
}
2, Bubble Sort, a basic algorithm in C, sorting a set of numbers from small to large.
Thought: This problem sorts from small to large, the first round sorts the smallest, the second round sorts the second smallest, the third round sorts the third smallest, and so on...
<?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]){//from small to large
$p = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $p;
}
}
}
var_dump($arr);
3, Pascal's Triangle, written in PHP.
Thought: The first and last characters of each line are1, there is no change, and the middle is the sum of the front row and the left row. This algorithm uses a two-dimensional array to save, and there is also an algorithm that can be implemented with a one-dimensional array, outputting line by line. If you are interested, you can try writing it for fun.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
<?php
//The first and last characters of each line are1, wrote6Line
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
}
}
//Print
for($i=0; $i<6; $i++{
for($j=0; $j<=$i; $j++) {
echo $a[$i][$j].' ';
}
echo '<br/>';
}
4To insert a number into a set of numbers, insert it in order according to its original sequence while maintaining the original sorting order.
The idea is to find the position of the number larger than the number to be inserted, replace it, and then shift the numbers behind it one position.
<?php
$in = 2;
$arr = array(1,1,1,3,5,7
$n = count($arr);
//If the number to be inserted is already the largest, print directly
if($arr[$n-1] < $in) {
$arr[$n+1] = $in; print_r($arr);
}
for($i=0; $i<$n; $i++) {
//Find the position to insert
if($arr[$i] >= $in){
$t1= $arr[$i];
$arr[$i] = $in;
//Shift the data behind one position
for($j=$i+1; $j<$n+1; $j++) {
$t2 = $arr[$j];
$arr[$j] = $t1;
$t1 = $t2;
}
//Print
print_r($arr);
die;
}
}
5To sort a set of numbers (quick sort algorithm).
The idea is to divide the array into two parts in one pass of sorting, then recursively sort these two parts, and finally merge them.
<?php
function q($array) {
if (count($array) <= 1) {return $array;}
//Divide into two subarrays with $key as the boundary
$key = $array[0];
$l = array();
$r = array();
//Sort separately and then combine into one 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) );
6To find the required element in an array (binary search algorithm).
The idea is to use an element in the array as a boundary, and then recursively search until the end.
<?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);
}
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)
7Merge multiple arrays without array_merge(), the question comes from the forum.
Approach: Traverse each array and reorganize into a new array.
<?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);
8Year of the Cow: There is a cow, by4years old can give birth, one cow each year, and all the offspring are female cows, by15years old is neutered and can no longer give birth,20 years old dies, how many cows will there be after n years? (From the forum)
<?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
====================Other Algorithms=========================
Bubble sort (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 (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 (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>';
}
Quick Sort (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);
}
=================================================
Bubble Sort: Swap the values pairwise, the smallest value is on the left, just like the lightest bubble is on the top. Swap the values pairwise in the entire sequence of numbers once, the smallest number is on the left, and each time you can get the smallest number in the remaining numbers, the 'emerged' numbers form an ordered interval, and the remaining values form an unordered interval, and each element value in the ordered interval is smaller than that in the unordered interval.
Quick Sort: Base number, two sub-arrays, recursive call, merge.
Insertion Sort: Divide the sorting interval into two parts, the left part is ordered and the right part is unordered. Take the first element from the right interval and insert it into the left interval. If this element is larger than the element at the rightmost end of the left interval, it stays in place. If this element is smaller than the element at the rightmost end of the left interval, it is inserted in the original position of the rightmost element, and the rightmost element moves one position to the right, the counter is decremented, and it is compared again with the previous elements until the previous elements are smaller than the element to be inserted. Repeat the above steps.
Note the handling of interval endpoint values, as well as the index of the first element of the array being 0.
<?php
//Common PHP Sorting Algorithms
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
/*
【Insertion sort (one-dimensional array）】
【Basic idea】：Each time, insert a data element to be sorted into the appropriate position in the already sorted sequence, maintaining the order of the sequence; until all the data elements to be sorted are inserted.
[Example]:
[Initial keyword] [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;
}
/*
【Selection sort (one-dimensional array）】
【Basic idea】：In each pass, select the smallest (or largest) element from the unsorted data elements and place it at the end of the already sorted sequence, until all the unsorted data elements are sorted.
[Example]:
[Initial keyword] [49 38 65 97 76 13 27 49]
After the first sort 13 ［38 65 97 76 49 27 49]
After the second sort 13 27 ［65 97 76 49 38 49]
After the third sort 13 27 38 [97 76 49 65 49]
After the fourth sort 13 27 38 49 [49 97 65 76]
After the fifth sort 13 27 38 49 49 [97 97 76]
After the sixth sort 13 27 38 49 49 76 [76 97]
After the seventh sort 13 27 38 49 49 76 76 [ 97]
The final sorting result 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;
}
/*
[Bubble Sort (one-dimensional array)]
[Basic Idea]: Compare the sizes of the elements to be sorted pairwise, and exchange them when the order of two elements is found to be reversed, until there are no elements in reverse order.
[Sorting Process]: Imagine the array R[1..N] are vertically standing, and each data element is regarded as a bubble with weight, according to the principle that light bubbles cannot be below heavy bubbles,
Scan the array R from bottom to top, whenever a light bubble that violates this principle is scanned, let it float up, and repeat this process repeatedly until finally any two bubbles are light ones on top and heavy ones on the bottom.
[Example]:
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;
}
/*
[Quick Sort (one-dimensional array)]
[Basic Idea]: In the current unordered area R[1Any element in R[
Use this base to divide the current unordered area into two smaller unordered areas: R[1..I-1] and R[I 1..H], and the data elements on the left are all less than or equal to the base element,
The data elements on the right are all greater than or equal to the base element, and the base X is located at the final sorted position, that is, R[1..I-1]≤X.Key≤R[I 1..H] (1≤I≤H),
When R[1..I-1] and R[I 1When all elements of the unordered subareas are sorted, the division process described above is performed on them respectively until all data elements in all unordered subareas are sorted.
[Example]:
Initial key [49 38 65 97 76 13 27 49］
After the first swap [27 38 65 97 76 13 49 49］
After the second swap [27 38 49 97 76 13 65 49］
J scans to the left, position unchanged, after the third swap [27 38 13 97 76 49 65 49］
I scans to the right, position unchanged, after the fourth swap [27 38 13 49 76 97 65 49］
J scans to the left [27 38 13 49 76 97 65 49］
(A division process)
Initial key values ［49 38 65 97 76 13 27 49］
After one sorting pass ［27 38 13］ 49 ［76 97 65 49］
After two sorting passes ［13］ 27 ［38］ 49 ［49 65］76 ［97］
After three sorting passes 13 27 38 49 49 ［65］76 97
The final sorting result 13 27 38 49 49 65 76 97
The state after each sorting pass
*/
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);
}
/*Print the entire content of the array*/
function display_arr($array){
$len = count($array);
for($i = 0; $i<$len; $i++{
echo $array[$i].' ';
}
echo '<br />';
}
/*
Comparison and selection of several sorting algorithms
1Factors to consider when selecting a sorting method:
(1The number of elements to be sorted, n;
(2The size of the information volume of the elements themselves;
(3The structure and distribution of the key values;
(4The conditions of the language tool, the size of the auxiliary space, etc.
2Summary:
(1If n is small (n < 50), direct insertion sort or direct selection sort can be used. Since direct insertion sort requires more record movement operations than direct selection sort, it is better to use direct selection sort when the record itself has a large information volume.
(2If the initial state of the file is already basically sorted by the key value, then it is advisable to use direct insertion or bubble sort.
(3If n is large, then a time complexity of O(nlogn) should be adopted.2n) sorting methods: quicksort, heapsort, or mergesort. Quicksort is currently considered the best method among the comparison-based internal sorting methods.
(4In the comparison-based sorting method, after comparing the sizes of two key values, only two possible transitions occur, so a binary tree can be used to describe the comparison decision process. It can be proven that when the n key values of a file are randomly distributed, any sorting algorithm that relies on "comparison" requires at least O(nlogn) time complexity.2n) time.
(5) When the record itself has a large amount of information, to avoid consuming a lot of time moving records, a linked list can be used as the storage structure.
*/
/*Sorting test*/
$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);
?>
/**
* Permutation and combination
* The selection of combinations using binary method, such as representing5choose3when, only need to have3the position is1is enough, so the combinations obtained are 01101 11100 00111 10011 01110equal10Combinations
*
* @param Array to be arranged $arr
* @param Minimum number $min_size
* @return The new array combination that meets the conditions
*/
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);
//Recursive Algorithm
//Factorial
function f($n){
if($n == 1 || $n == 0){
return 1;
}
return $n*f($n-1
}
}
echo f(5
//Traverse directories
$filearr = array();
}
if(is_dir($file)){*}
$filearr = array_merge($filearr, iteral($file));
else{
}
$filearr[] = $file;
}
}
return $filearr;
}
var_dump(iteral('d:\www\test'));
Readers who are interested in more PHP-related content can check out the special topics on this site: 'PHP Data Structures and Algorithms Tutorial', 'Summary of PHP Program Design Algorithms', 'Summary of PHP Encryption Methods', 'Summary of PHP Encoding and Decoding Operation Skills', 'PHP Object-Oriented Program Design Tutorial', 'Summary of PHP Mathematical Operation Skills', 'Comprehensive Skills of PHP Array (Array) Operation', 'Summary of PHP String (string) Usage', 'Summary of PHP Regular Expression Usage', and 'Summary of Common Database Operation Skills in PHP'.
I hope the tutorial described in this article is helpful to everyone's PHP program design.
Declaration: The content of this article is from the network, and the copyright belongs to the original author. The content is contributed and uploaded by Internet users spontaneously. This website does not own the copyright, has not been edited by humans, and does not assume any relevant legal liability. If you find any suspected copyright content, please send an email to: notice#oldtoolbag.com (when sending an email, please replace # with @ to report, and provide relevant evidence. Once verified, this site will immediately delete the infringing content.)