PHP realizes the classic algorithm under php7 PHP environment construction PHP from entry to proficiency-PHP Tutorial-php.cn

Home

Backend Development

PHP Tutorial

PHP realizes the classic algorithm under php7 PHP environment construction PHP from entry to proficiency

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jul 29, 2016 am 08:53 AM

php

Foreword

A few days ago, we implemented different sorting algorithms through PHP and compared the corresponding time-consuming of the algorithms.
[Algorithm] PHP implements the classic algorithm (Part 1)

Let’s implement the following algorithm

Heap sort
Cocktail sort
Direct selection sort
Counting sort

CODE

<code><span>$arr</span> = [];

<span>for</span> (<span>$i</span> = <span>0</span>; <span>$i</span> < <span>5000</span>; <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> < <span>$heapsize</span> && <span>$left</span> < <span>$heapsize</span>  && <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> < <span>$heapsize</span> && <span>$right</span> < <span>$heapsize</span> && <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> < <span>$heapsize</span> && <span>$max</span> < <span>$heapsize</span>){

        <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> < (<span>$arr_len</span>/<span>2</span>) ; <span>$i</span> ++){
        <span>//将最小值排到队尾</span><span>for</span>( <span>$j</span> = <span>$i</span> ; <span>$j</span> < ( <span>$arr_len</span> - <span>$i</span> - <span>1</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>//将最大值排到队头</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><<span>$n</span>;++<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>] < <span>$arr</span>[<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> < <span>$n</span> - <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> < <span>$n</span>; <span>$j</span>++){
            <span>if</span>(<span>$arr</span>[<span>$j</span>] < <span>$arr</span>[<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> < <span>$min</span>) {
            <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> < count(<span>$arr</span>) ; <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> < count(<span>$c</span>); ++<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>

Copy after login

Time-consuming comparison

Heap Sorting time: 0.086709976196289
Cocktail sorting time: 4.6467659473419
Hill sorting time: 4.4215688705444
Direct selection sorting time: 4.529422044754
Counting sorting takes time: 4.2601070404053

References

Introduction to Algorithms

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

The above introduces the implementation of classic algorithms in PHP, including PHP content. I hope it will be helpful to friends who are interested in PHP tutorials.

Statement of this Website

The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress images for free

Clothoff.io

AI clothes remover

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)

4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

R.E.P.O. Best Graphic Settings

4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Assassin's Creed Shadows: Seashell Riddle Solution

2 weeks ago By DDD

R.E.P.O. How to Fix Audio if You Can't Hear Anyone

4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

R.E.P.O. Chat Commands and How to Use Them

4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Hot Topics

Where is the login entrance for gmail email?

7527

CakePHP Tutorial

1378

What is the format of the account name of steam

win11 activation key permanent

nyt connections hints and answers

Related knowledge

PHP 8.4 Installation and Upgrade guide for Ubuntu and Debian Dec 24, 2024 pm 04:42 PM

PHP 8.4 brings several new features, security improvements, and performance improvements with healthy amounts of feature deprecations and removals. This guide explains how to install PHP 8.4 or upgrade to PHP 8.4 on Ubuntu, Debian, or their derivati

How To Set Up Visual Studio Code (VS Code) for PHP Development Dec 20, 2024 am 11:31 AM

Visual Studio Code, also known as VS Code, is a free source code editor — or integrated development environment (IDE) — available for all major operating systems. With a large collection of extensions for many programming languages, VS Code can be c

7 PHP Functions I Regret I Didn't Know Before Nov 13, 2024 am 09:42 AM

If you are an experienced PHP developer, you might have the feeling that you’ve been there and done that already.You have developed a significant number of applications, debugged millions of lines of code, and tweaked a bunch of scripts to achieve op

How do you parse and process HTML/XML in PHP? Feb 07, 2025 am 11:57 AM

This tutorial demonstrates how to efficiently process XML documents using PHP. XML (eXtensible Markup Language) is a versatile text-based markup language designed for both human readability and machine parsing. It's commonly used for data storage an

Explain JSON Web Tokens (JWT) and their use case in PHP APIs. Apr 05, 2025 am 12:04 AM

JWT is an open standard based on JSON, used to securely transmit information between parties, mainly for identity authentication and information exchange. 1. JWT consists of three parts: Header, Payload and Signature. 2. The working principle of JWT includes three steps: generating JWT, verifying JWT and parsing Payload. 3. When using JWT for authentication in PHP, JWT can be generated and verified, and user role and permission information can be included in advanced usage. 4. Common errors include signature verification failure, token expiration, and payload oversized. Debugging skills include using debugging tools and logging. 5. Performance optimization and best practices include using appropriate signature algorithms, setting validity periods reasonably,

PHP Program to Count Vowels in a String Feb 07, 2025 pm 12:12 PM

A string is a sequence of characters, including letters, numbers, and symbols. This tutorial will learn how to calculate the number of vowels in a given string in PHP using different methods. The vowels in English are a, e, i, o, u, and they can be uppercase or lowercase. What is a vowel? Vowels are alphabetic characters that represent a specific pronunciation. There are five vowels in English, including uppercase and lowercase: a, e, i, o, u Example 1 Input: String = "Tutorialspoint" Output: 6 explain The vowels in the string "Tutorialspoint" are u, o, i, a, o, i. There are 6 yuan in total

Explain late static binding in PHP (static::). Apr 03, 2025 am 12:04 AM

Static binding (static::) implements late static binding (LSB) in PHP, allowing calling classes to be referenced in static contexts rather than defining classes. 1) The parsing process is performed at runtime, 2) Look up the call class in the inheritance relationship, 3) It may bring performance overhead.

What are PHP magic methods (__construct, __destruct, __call, __get, __set, etc.) and provide use cases? Apr 03, 2025 am 12:03 AM

What are the magic methods of PHP? PHP's magic methods include: 1.\_\_construct, used to initialize objects; 2.\_\_destruct, used to clean up resources; 3.\_\_call, handle non-existent method calls; 4.\_\_get, implement dynamic attribute access; 5.\_\_set, implement dynamic attribute settings. These methods are automatically called in certain situations, improving code flexibility and efficiency.

See all articles