PHP实现经典算法下 php7 php环境搭建 php从入门到精通
前言
前几天,我们通过PHP实现了不同的排序算法,并比较算法对应的耗时。
【算法】PHP实现经典算法(上)
下面我们来实现下列算法
- 堆排序
- 鸡尾酒排序
- 直接选择排序
- 计数排序
CODE
<code><span>$arr</span> = []; <span>for</span> (<span>$i</span> = <span>0</span>; <span>$i</span> 5000; <span>$i</span>++) { <span>$arr</span>[] = rand(<span>1</span>, <span>50000</span>); } <span>// 5 堆排序</span><span>/** * 交换两个数的位置 *<span> @param</span> $a *<span> @param</span> $b */</span><span><span>function</span><span>swap</span><span>(&<span>$a</span>,&<span>$b</span>)</span>{</span><span>$temp</span> = <span>$b</span>; <span>$b</span> = <span>$a</span>; <span>$a</span> = <span>$temp</span>; } <span>/** * 左子树 *<span> @param</span> $i *<span> @return</span> mixed */</span><span><span>function</span><span>lchild</span><span>(<span>$i</span>)</span>{</span><span>return</span><span>$i</span>*<span>2</span>+<span>1</span>;} <span>/** * 右子树 *<span> @param</span> $i *<span> @return</span> mixed */</span><span><span>function</span><span>rchild</span><span>(<span>$i</span>)</span>{</span><span>return</span><span>$i</span>*<span>2</span>+<span>2</span>;} <span>/** * 整理节点 *<span> @param</span> $array 待调整的堆数组 *<span> @param</span> $i 待调整的数组元素的位置 *<span> @param</span> $heapsize 数组的长度 */</span><span><span>function</span><span>build_heap</span><span>(&<span>$array</span>,<span>$i</span>,<span>$heapsize</span>)</span>{</span><span>$left</span> = lchild(<span>$i</span>); <span>$right</span> = rchild(<span>$i</span>); <span>$max</span> = <span>$i</span>; <span>//如果比左子树小并且在左右子树的右面,边界调整到左侧</span><span>if</span>(<span>$i</span> $heapsize && <span>$left</span> $heapsize && <span>$array</span>[<span>$left</span>] > <span>$array</span>[<span>$i</span>] ){ <span>$max</span> = <span>$left</span>; } <span>//如果比右子树小并且都小于要构建的数组长度,边界调整到右侧</span><span>if</span>(<span>$i</span> $heapsize && <span>$right</span> $heapsize && <span>$array</span>[<span>$right</span>] > <span>$array</span>[<span>$max</span>]){ <span>$max</span> = <span>$right</span>; } <span>//如果经过两次调整后,要调整的数组不是最大值</span><span>if</span>(<span>$i</span> != <span>$max</span> && <span>$i</span> $heapsize && <span>$max</span> $heapsize){ <span>//就交换对应的位置,并再次进行整理节点</span> swap(<span>$array</span>[<span>$i</span>],<span>$array</span>[<span>$max</span>]); build_heap(<span>$array</span>,<span>$max</span>,<span>$heapsize</span>); } } <span>/** * 对堆进行排序 *<span> @param</span> $array 要排序的数组 *<span> @param</span> $heapsize 数组的长度 */</span><span><span>function</span><span>sortHeap</span><span>(&<span>$array</span>,<span>$heapsize</span>)</span>{</span><span>while</span>(<span>$heapsize</span>){ <span>//长度逐步递减0</span><span>//首先交换第一个元素和最后一个元素的位置</span> swap(<span>$array</span>[<span>0</span>],<span>$array</span>[<span>$heapsize</span>-<span>1</span>]); <span>$heapsize</span> = <span>$heapsize</span> -<span>1</span>; build_heap(<span>$array</span>,<span>0</span>,<span>$heapsize</span>); <span>//整理数组的第一个的元素的位置,长度为逐步递减的数组长度</span> } } <span>/** * 创建堆 *<span> @param</span> $array *<span> @param</span> $heapsize */</span><span><span>function</span><span>createHeap</span><span>(&<span>$array</span>,<span>$heapsize</span>)</span>{</span><span>$i</span> = ceil(<span>$heapsize</span>/<span>2</span>)-<span>1</span>; <span>//找到中间的位置</span><span>for</span>( ; <span>$i</span>>=<span>0</span> ;<span>$i</span>-- ){ <span>//从中间往前面整理堆</span> build_heap(<span>$array</span>,<span>$i</span>,<span>$heapsize</span>); } } <span>/** * 堆排序主函数 */</span><span><span>function</span><span>Heapsort</span><span>(<span>$array</span>)</span>{</span><span>$heapsize</span> = count(<span>$array</span>); createHeap(<span>$array</span>,<span>$heapsize</span>); sortHeap(<span>$array</span>,<span>$heapsize</span>); <span>return</span><span>$array</span>; } <span>$heapsort_start_time</span> = microtime(<span>true</span>); <span>$heapsort_sort</span> = Heapsort(<span>$arr</span>); <span>$heapsort_end_time</span> = microtime(<span>true</span>); <span>$heapsort_need_time</span> = <span>$heapsort_end_time</span> - <span>$heapsort_start_time</span>; print_r(<span>"堆排序耗时:"</span> . <span>$heapsort_need_time</span> . <span>"<br>"</span>); <span>// 6 鸡尾酒排序法</span><span>/** * 鸡尾酒排序 *<span> @param</span> $arr *<span> @return</span> mixed */</span><span><span>function</span><span>Cocktailsort</span><span>(<span>$arr</span>)</span> {</span><span>$arr_len</span> =count(<span>$arr</span>); <span>for</span>(<span>$i</span> = <span>0</span> ; <span>$i</span> $arr_len/<span>2</span>) ; <span>$i</span> ++){ <span>//将最小值排到队尾</span><span>for</span>( <span>$j</span> = <span>$i</span> ; <span>$j</span> $arr_len - <span>$i</span> - <span>1</span> ) ; <span>$j</span> ++ ){ <span>if</span>(<span>$arr</span>[<span>$j</span>] $arr[<span>$j</span> + <span>1</span>] ){ swap(<span>$arr</span>[<span>$j</span>],<span>$arr</span>[<span>$j</span> + <span>1</span>]); } } <span>//将最大值排到队头</span><span>for</span>(<span>$j</span> = <span>$arr_len</span> - <span>1</span> - (<span>$i</span> + <span>1</span>); <span>$j</span> > <span>$i</span> ; <span>$j</span> --){ <span>if</span>(<span>$arr</span>[<span>$j</span>] > <span>$arr</span>[<span>$j</span> - <span>1</span>]){ swap(<span>$arr</span>[<span>$j</span>],<span>$arr</span>[<span>$j</span> - <span>1</span>]); } } } <span>return</span><span>$arr</span>; } <span>$cocktailsort_start_time</span> = microtime(<span>true</span>); <span>$cocktailsort_sort</span> = Cocktailsort(<span>$arr</span>); <span>$cocktailsortt_end_time</span> = microtime(<span>true</span>); <span>$cocktailsort_need_time</span> = <span>$cocktailsortt_end_time</span> - <span>$cocktailsort_start_time</span>; print_r(<span>"鸡尾酒排序耗时:"</span> . <span>$cocktailsort_need_time</span> . <span>"<br>"</span>); <span>// 7 希尔排序</span><span>/** * 希尔排序 *<span> @param</span> $arr */</span><span><span>function</span><span>Shellsort</span><span>(<span>$arr</span>)</span> {</span><span>$n</span>=count(<span>$arr</span>); <span>//数组长度</span><span>for</span>(<span>$gap</span>=floor(<span>$n</span>/<span>2</span>);<span>$gap</span>><span>0</span>;<span>$gap</span>=floor(<span>$gap</span>/=<span>2</span>)) <span>//</span> { <span>for</span>(<span>$i</span>=<span>$gap</span>;<span>$i</span>$n;++<span>$i</span>) <span>//根据增量循环</span> { <span>//以增量为步幅进行查看</span><span>for</span>( <span>$j</span>=<span>$i</span>-<span>$gap</span>; <span>$j</span>>=<span>0</span> && <span>$arr</span>[<span>$j</span>+<span>$gap</span>] $arr[<span>$j</span>]; <span>$j</span> -= <span>$gap</span>) { swap(<span>$arr</span>[<span>$j</span>],<span>$arr</span>[<span>$j</span>+<span>$gap</span>]); } } } <span>return</span><span>$arr</span>; } <span>$shellsort_start_time</span> = microtime(<span>true</span>); <span>$shellsort_sort</span> = Cocktailsort(<span>$arr</span>); <span>$shellsort_end_time</span> = microtime(<span>true</span>); <span>$shellsort_need_time</span> = <span>$shellsort_end_time</span> - <span>$shellsort_start_time</span>; print_r(<span>"希尔排序耗时:"</span> . <span>$shellsort_need_time</span> . <span>"<br>"</span>); <span>// 8 直接选择排序</span><span>/** * 直接选择排序 *<span> @param</span> $arr *<span> @return</span> mixed */</span><span><span>function</span><span>Straightselectsort</span><span>(<span>$arr</span>)</span>{</span><span>$n</span> = count(<span>$arr</span>); <span>for</span>(<span>$i</span> = <span>0</span> ; <span>$i</span> $n - <span>1</span>;<span>$i</span>++){ <span>$m</span> = <span>$i</span>; <span>for</span>(<span>$j</span> = <span>$i</span>+<span>1</span> ; <span>$j</span> $n; <span>$j</span>++){ <span>if</span>(<span>$arr</span>[<span>$j</span>] $arr[<span>$m</span>] ){ <span>$m</span> = <span>$j</span>; } <span>if</span>(<span>$m</span> != <span>$j</span>){ <span>//进行交换</span> swap(<span>$arr</span>[<span>$m</span>],<span>$arr</span>[<span>$j</span>]); } } } <span>return</span><span>$arr</span>; } <span>$straightselectsort_start_time</span> = microtime(<span>true</span>); <span>$straightselectsort_sort</span> = Cocktailsort(<span>$arr</span>); <span>$straightselectsort_end_time</span> = microtime(<span>true</span>); <span>$straightselectsort_need_time</span> = <span>$straightselectsort_end_time</span> - <span>$straightselectsort_start_time</span>; print_r(<span>"直接选择排序耗时:"</span> . <span>$straightselectsort_need_time</span> . <span>"<br>"</span>); <span>// 9 计数排序</span><span>/** * 计数排序 *<span> @param</span> $arr *<span> @return</span> mixed */</span><span><span>function</span><span>Countsort</span><span>(<span>$arr</span>)</span>{</span><span>$max</span> = <span>$arr</span>[<span>0</span>]; <span>$min</span> = <span>$arr</span>[<span>0</span>]; <span>foreach</span>(<span>$arr</span><span>as</span><span>$key</span> => <span>$value</span>) { <span>if</span> (<span>$value</span> > <span>$max</span>) { <span>$max</span> = <span>$value</span>; } <span>if</span> (<span>$value</span> $min) { <span>$min</span> = <span>$value</span>; } } <span>//这里k的大小是要排序的数组中,元素大小的极值差+1</span><span>$c</span>=[]; <span>$k</span> = <span>$max</span> - <span>$min</span> + <span>1</span>; <span>for</span>(<span>$i</span> = <span>0</span>; <span>$i</span> $arr) ; <span>$i</span> ++){ <span>$c</span>[<span>$arr</span>[<span>$i</span>] - <span>$min</span> ] +=<span>1</span>; } <span>for</span>(<span>$i</span>=<span>1</span>;<span>$i</span> $c); ++<span>$i</span>){ <span>$c</span>[<span>$i</span>] = <span>$c</span>[<span>$i</span>] + <span>$c</span>[<span>$i</span> - <span>1</span>]; } <span>for</span>(<span>$i</span> = count(<span>$arr</span>);<span>$i</span> > <span>0</span> ; --<span>$i</span>){ <span>$b</span>[ -- <span>$c</span>[<span>$arr</span>[<span>$i</span>] - <span>$min</span>] ] = <span>$arr</span>[<span>$i</span>]; } <span>return</span><span>$b</span>; } <span>$countsort_start_time</span> = microtime(<span>true</span>); <span>$countsort_sort</span> = Cocktailsort(<span>$arr</span>); <span>$countsort_end_time</span> = microtime(<span>true</span>); <span>$countsort_need_time</span> = <span>$countsort_end_time</span> - <span>$countsort_start_time</span>; print_r(<span>"计数排序耗时:"</span> . <span>$countsort_need_time</span> . <span>"<br>"</span>); </code>
耗时对比
堆排序耗时:0.086709976196289
鸡尾酒排序耗时:4.6467659473419
希尔排序耗时:4.4215688705444
直接选择排序耗时:4.529422044754
计数排序耗时:4.2601070404053
参考资料
- 算法导论
以上就介绍了PHP实现经典算法下,包括了php方面的内容,希望对PHP教程有兴趣的朋友有所帮助。

Heiße KI -Werkzeuge

Undresser.AI Undress
KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover
Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool
Ausziehbilder kostenlos

Clothoff.io
KI-Kleiderentferner

AI Hentai Generator
Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

Heiße Werkzeuge

Notepad++7.3.1
Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version
Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1
Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6
Visuelle Webentwicklungstools

SublimeText3 Mac-Version
Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Heiße Themen



In diesem Kapitel werden wir die Umgebungsvariablen, die allgemeine Konfiguration, die Datenbankkonfiguration und die E-Mail-Konfiguration in CakePHP verstehen.

PHP 8.4 bringt mehrere neue Funktionen, Sicherheitsverbesserungen und Leistungsverbesserungen mit einer beträchtlichen Menge an veralteten und entfernten Funktionen. In dieser Anleitung wird erklärt, wie Sie PHP 8.4 installieren oder auf PHP 8.4 auf Ubuntu, Debian oder deren Derivaten aktualisieren. Obwohl es möglich ist, PHP aus dem Quellcode zu kompilieren, ist die Installation aus einem APT-Repository wie unten erläutert oft schneller und sicherer, da diese Repositorys in Zukunft die neuesten Fehlerbehebungen und Sicherheitsupdates bereitstellen.

Um in cakephp4 mit Datum und Uhrzeit zu arbeiten, verwenden wir die verfügbare FrozenTime-Klasse.

Das Arbeiten mit der Datenbank in CakePHP ist sehr einfach. In diesem Kapitel werden wir die CRUD-Operationen (Erstellen, Lesen, Aktualisieren, Löschen) verstehen.

Um am Datei-Upload zu arbeiten, verwenden wir den Formular-Helfer. Hier ist ein Beispiel für den Datei-Upload.

In diesem Kapitel lernen wir die folgenden Themen im Zusammenhang mit dem Routing kennen.

CakePHP ist ein Open-Source-Framework für PHP. Es soll die Entwicklung, Bereitstellung und Wartung von Anwendungen erheblich vereinfachen. CakePHP basiert auf einer MVC-ähnlichen Architektur, die sowohl leistungsstark als auch leicht zu verstehen ist. Modelle, Ansichten und Controller gu

Der Validator kann durch Hinzufügen der folgenden zwei Zeilen im Controller erstellt werden.
