Heim > Backend-Entwicklung > PHP-Tutorial > 基数排序的PHP实现

基数排序的PHP实现

WBOY
Freigeben: 2016-07-29 08:59:54
Original
978 Leute haben es durchsucht

基数排序是根据关键字中各位的值,通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。

不妨通过一个具体的实例来展示一下,基数排序是如何进行的。
设有一个初始序列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。
我们知道,任何一个阿拉伯数,它的各个位数上的基数都是以0~9来表示的。
所以我们不妨把0~9视为10个桶。
我们先根据序列的个位数的数字来进行分类,将其分到指定的桶中。例如:R[0] = 50,个位数上是0,将这个数存入编号为0的桶中。
基数排序的PHP实现
分类后,我们在从各个桶中,将这些数按照从编号0到编号9的顺序依次将所有数取出来。

这时,得到的序列就是个位数上呈递增趋势的序列。
按照个位数排序: {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。
接下来,可以对十位数、百位数也按照这种方法进行排序,最后就能得到排序完成的序列。

<code><span><span><span><?php </span>
/**基数排序**/</span><span>/*
* 获取第几位上的数字
*
*百位数 = 2345%1000/100
*/</span><span><span>function</span><span>getN</span><span>(<span>$num</span>,<span>$N</span>)</span>{</span><span>$value</span> = <span>10</span>;
    <span>for</span>(<span>$i</span>=<span>1</span>;<span>$i</span>$N</span>;<span>$i</span>++){
        <span>$value</span> = <span>$value</span> * <span>10</span>; 
    }

    <span>$M</span> = (int)((<span>$num</span> % <span>$value</span> /(<span>$value</span>/<span>10</span>)));
    <span>return</span><span>$M</span>;
}
<span>/*
*/</span><span><span>function</span><span>paixu</span><span>(<span>$arr</span>)</span>
{</span><span>$flag</span> = <span>1</span>;<span>//该次位数上是否全为0标志位,全为0 flag=0</span><span>for</span>(<span>$M</span>=<span>1</span>;<span>$flag</span>!=<span>0</span>;<span>$M</span>++)
    {
        <span>$flag</span> = <span>0</span>;

        <span>if</span>(<span>$M</span> > <span>1</span>){
            <span>$m</span> = <span>0</span>;
            <span>for</span>(<span>$j</span>=<span>0</span>;<span>$j</span>10</span>;<span>$j</span>++){
                <span>for</span>(<span>$k</span>=<span>0</span>;<span>$k</span><count>$b[<span>$j</span>]);<span>$k</span>++){
                    <span>if</span>(<span>$b</span>[<span>$j</span>][<span>$k</span>]!=<span>0</span>)
                    <span>$arr</span>[<span>$m</span>++] = <span>$b</span>[<span>$j</span>][<span>$k</span>];<span>//将容器中的数按序取出,进行下一次排序</span>
                }

            }
            <span>$b</span> = <span>array</span>();<span>//再给b附新值前要清空数组中原有的数据</span>
        }

        <span>for</span>(<span>$i</span>=<span>0</span>;<span>$i</span><count>$arr);<span>$i</span>++)
        {
            <span>$thisNum</span> = getN(<span>$arr</span>[<span>$i</span>],<span>$M</span>);
            <span>if</span>(<span>$thisNum</span>!=<span>0</span>) <span>$flag</span> = <span>1</span>;
            <span>$b</span>[<span>$thisNum</span>][] = <span>$arr</span>[<span>$i</span>];<span>//将数组中的数放入容器中</span>        }

    }
    print_r(<span>$arr</span>);
    <span>//var_dump($b);</span>}
<span>/**基数排序**结束**/</span><span>?></span></count></count></code>
Nach dem Login kopieren

paixu(array(65,3,45,6,7,8,31,100,1000,1234))
结果为:Array ( [0] => 3 [1] => 6 [2] => 7 [3] => 8 [4] => 31 [5] => 45 [6] => 65 [7] => 100 [8] => 1000 [9] => 1234 )

基数排序还可以应用在查找重复数,查找间隔数等方面
代码不重要(我的代码仍需改进),思路是关键

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

以上就介绍了基数排序的PHP实现,包括了方面的内容,希望对PHP教程有兴趣的朋友有所帮助。

Verwandte Etiketten:
Quelle:php.cn
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
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage