Dieser Artikel stellt hauptsächlich eine Sammlung klassischer PHP-Algorithmen vor und sortiert verschiedene gängige Algorithmen, einschließlich verschiedener gängiger Algorithmusprinzipien und Implementierungstechniken wie Sortieren, Suchen, Durchlaufen und Betrieb. Freunde in Not können darauf verweisen
Die Beispiele in diesem Artikel fassen die klassischen PHP-Algorithmen zusammen. Teilen Sie es als Referenz mit allen:
1. Zeichnen wir es zunächst zum Spaß in Büchern. Zeichnen wir es in PHP Zeichne die Hälfte davon.
Idee: einmal für so viele Zeilen, und dann einmal für Leerzeichen und Sternchen drin.
1 2 3 4 5 6 | <?php
for ( $i =0; $i <=3; $i ++){
echo str_repeat ( " " ,3- $i );
echo str_repeat ( "*" , $i *2+1);
echo '<br/>';
}
|
Nach dem Login kopieren
2. Die Blasensortierung, der grundlegende Algorithmus in C, sortiert eine Reihe von Zahlen von klein nach groß.
Idee: Von klein bis groß: In der ersten Runde werden die Kleinsten eingestuft, in der zweiten Runde die zweitkleinsten, in der dritten Runde die drittkleinsten und so weiter ...
1 2 3 4 5 6 7 8 9 10 11 12 13 | <?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 );
|
Nach dem Login kopieren
3. Yang Hui Dreieck, geschrieben in PHP.
Idee: Die erste und letzte Ziffer jeder Zeile sind 1 und es gibt keine Änderung. Die Mitte ist die Summe der vorderen und linken Zeile. Dieser Algorithmus wird in einem zweidimensionalen Array gespeichert. und es gibt Dieser Algorithmus kann auch mit einem eindimensionalen Array implementiert werden und die Ausgabe erfolgt zeilenweise. Wenn Sie interessiert sind, können Sie ihn aufschreiben und damit spielen.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | <?php
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/>';
}
|
Nach dem Login kopieren
4. In einem Zahlensatz ist es erforderlich, eine Zahl in ihrer ursprünglichen Reihenfolge einzufügen und die ursprüngliche Sortiermethode beizubehalten.
Idee: Suchen Sie die Position, die größer als die einzufügende Zahl ist, ersetzen Sie sie und verschieben Sie dann die folgende Nummer eins.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | <?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 ;
}
}
|
Nach dem Login kopieren
5. Sortieren Sie eine Reihe von Zahlen (Schnellsortieralgorithmus).
Idee: Teilen Sie es durch eine Sortierung in zwei Teile, sortieren Sie dann die beiden Teile rekursiv und führen Sie sie schließlich zusammen.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | <?php
function q( $array ) {
if ( count ( $array ) <= 1) { return $array ;}
$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 ) );
|
Nach dem Login kopieren
6. Suchen Sie das benötigte Element in einem Array (binärer Suchalgorithmus).
Idee: Verwenden Sie einen bestimmten Wert im Array als Grenze und suchen Sie dann rekursiv bis zum Ende.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | <?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...');
}
$array = array (2,4,3,5);
$n = count ( $array );
$r = find( $array ,0, $n ,5)
|
Nach dem Login kopieren
7. Mehrere Arrays ohne array_merge() zusammenführen. Die Frage kommt aus dem Forum.
Idee: Jedes Array durchlaufen und ein neues Array rekonstruieren.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | <?php
function t(){
$c = func_num_args()-1;
$a = func_get_args();
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 ;
}
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 );
|
Nach dem Login kopieren
8. Bitten Sie im Jahr des Ochsen um eine Kuh: Es gibt eine Kuh, die gebären kann bis 4 Jahre alt, eine Kuh pro Jahr, und die Anzahl der Nachkommen ist gleich. Sie wird im Alter von 15 Jahren sterilisiert und kann im Alter von 20 Jahren nicht mehr gebären wird es in n Jahren so sein? (aus dem Forum)
1 2 3 4 5 6 7 8 9 10 11 | <?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 ;
}
echo t(8);
|
Nach dem Login kopieren
================== == =Andere Algorithmen==========================
Blasensortierung (Blasensortierung) – O(n2)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | $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 '
|
';
}
Nach dem Login kopieren
Einfügungssortierung (Einfügungssortierung) – O(n2)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | $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 '
|
';
}
Nach dem Login kopieren
Hill-Sortierung (Shell-Sortierung) – O(n log n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | $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 '
|
';
}
Nach dem Login kopieren
Quicksort (Quicksort) – O(n log n)
1 2 3 4 5 6 | $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);
}
Nach dem Login kopieren
========= = ======================================
Blasensortierung: Tauschen Sie die Werte paarweise aus, wobei der kleinste Wert ganz links steht, genau wie die hellste Blase oben. Vertauschen Sie die gesamte Zahlenspalte einmal, wobei die kleinste Zahl ganz links steht. Sie können jedes Mal die kleinste Zahl unter den verbleibenden Zahlen erhalten. Die „geplatzten“ Zahlen bilden ein geordnetes Intervall, und die verbleibenden Werte bilden ein An ungeordnetes Intervall, und der Wert jedes Elements im geordneten Intervall ist kleiner als der des ungeordneten Intervalls.
Schnellsortierung: Basiszahl, linke und rechte Arrays, rekursiver Aufruf, Zusammenführung.
Einfügesortierung: Der Sortierbereich ist in zwei Teile unterteilt, der linke ist geordnet und der rechte ist ungeordnet. Nehmen Sie das erste Element aus dem rechten Bereich und fügen Sie es in den linken Bereich ein Lassen Sie das Element ganz rechts im linken Bereich dort, wo es ist. Wenn dieses Element kleiner als das Element ganz rechts im linken Bereich ist, wird es an der ursprünglichen Position des Elements ganz rechts und gleichzeitig ganz rechts eingefügt Das Element wird um eine Position nach rechts verschoben, der Rechner wird um eins verkleinert und das vorherige Element wird erneut verglichen, bis das vorherige Element kleiner als das vorherige Element ist. Wiederholen Sie die obigen Schritte, bis das eingefügte Element kleiner ist.
Achten Sie auf die Verarbeitung von Intervallendpunktwerten. Der Index des ersten Elements des Arrays ist 0.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | <?php
function bubblesort ( $array )
{
$n = count ( $array );
for ( $i = 0; $i < $n ; $i ++)
{
for ( $j = $n - 2; $j >= $i ; $j --)
{
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 ++)
{
$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 ));
?>
|
Nach dem Login kopieren
=======================================
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 | <?php
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 ;
}
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 ;
}
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 ;
}
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 />';
}
$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 );
?>
|
Nach dem Login kopieren
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
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'));
|
Nach dem Login kopieren
Verwandte Empfehlungen:
Beispielanalyse für den klassischen PHP-Algorithmus
Der klassische PHP-Algorithmus überquert die Brücke
Das obige ist der detaillierte Inhalt vonEine Sammlung klassischer PHP-Algorithmen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!