PHPはphp7で古典的なアルゴリズムを実現 PHP環境構築 PHP入門から習熟まで

前書き

数日前、私たちは PHP を介してさまざまな並べ替えアルゴリズムを実装し、対応するアルゴリズムの所要時間を比較しました。
【アルゴリズム】PHPで古典的なアルゴリズムを実装する(前編)

次のアルゴリズムを実装してみましょう

• ヒープソート
• カクテルソート
• 直接選択ソート
• カウンティングソート

コード

<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>

時間のかかる比較

ヒープソート時間: 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 チュートリアルに興味のある友人に役立つことを願っています。