Heim Backend-Entwicklung PHP-Tutorial PHP实现经典算法下 php7 php环境搭建 php从入门到精通

PHP实现经典算法下 php7 php环境搭建 php从入门到精通

Jul 29, 2016 am 08:53 AM
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>
Nach dem Login kopieren

耗时对比

堆排序耗时:0.086709976196289
鸡尾酒排序耗时:4.6467659473419
希尔排序耗时:4.4215688705444
直接选择排序耗时:4.529422044754
计数排序耗时:4.2601070404053

参考资料

  • 算法导论
').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i ').text(i)); }; $numbering.fadeIn(1700); }); });

以上就介绍了PHP实现经典算法下,包括了php方面的内容,希望对PHP教程有兴趣的朋友有所帮助。

Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

AI Hentai Generator

AI Hentai Generator

Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

R.E.P.O. Energiekristalle erklärten und was sie tun (gelber Kristall)
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Beste grafische Einstellungen
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. So reparieren Sie Audio, wenn Sie niemanden hören können
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌

Heiße Werkzeuge

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

CakePHP-Projektkonfiguration CakePHP-Projektkonfiguration Sep 10, 2024 pm 05:25 PM

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

PHP 8.4 Installations- und Upgrade-Anleitung für Ubuntu und Debian PHP 8.4 Installations- und Upgrade-Anleitung für Ubuntu und Debian Dec 24, 2024 pm 04:42 PM

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.

CakePHP Datum und Uhrzeit CakePHP Datum und Uhrzeit Sep 10, 2024 pm 05:27 PM

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

CakePHP arbeitet mit Datenbank CakePHP arbeitet mit Datenbank Sep 10, 2024 pm 05:25 PM

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

CakePHP-Datei hochladen CakePHP-Datei hochladen Sep 10, 2024 pm 05:27 PM

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

CakePHP-Routing CakePHP-Routing Sep 10, 2024 pm 05:25 PM

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

Besprechen Sie CakePHP Besprechen Sie CakePHP Sep 10, 2024 pm 05:28 PM

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

CakePHP erstellt Validatoren CakePHP erstellt Validatoren Sep 10, 2024 pm 05:26 PM

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

See all articles