Community Learn Tools Library Leisure
search
English
Home > Backend Development > PHP Tutorial > PHP realizes the classic algorithm under php7 PHP environment construction PHP from entry to proficiency

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

WBOY
Release： 2016-07-29 08:53:45
Original
1026 people have browsed it

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.

Related labels：
php
source：php.cn
Previous article：The variable "define as you use" function in PWP pwcorr txtpw pw public Next article：nginx proxy has data truncation problem nginx apache nginx php nginx rewrite
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
Latest Articles by Author
Latest Issues
PHP arrays obtained from URL parameters do not behave as expected I have a URL parameter that contains the category ID and I want to treat it as an array li...
From 2024-04-06 22:09:02
0
1
1428
Where should I place CustomLog directive in apache I'm using php:7.2-apachedocker. I need to disable health check url login access log. Based...
From 2024-04-06 22:03:59
0
1
990
What is the format of the variables in the return value? I am a new learner of php. I found a piece of code: if($x<time()){return[false,'error']...
From 2024-04-06 21:55:20
0
1
778
Problems encountered when using opentbs to generate odt files: values ​​of the same key are displayed in the same row instead of separate columns. I'm using a library called OpenTbs to create odt using PHP, I'm using it because columns a...
From 2024-04-06 20:18:18
0
1
483
Group MySQL results by ID for looping over I have a table with flight data in mysql. I'm writing a php code that will group and displ...
From 2024-04-06 17:27:56
0
1
406
Related Topics
More>
Popular Recommendations
Popular Tutorials
More>
Related Tutorials
Popular Recommendations
Latest courses
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template