未加星标

PHP实现基数排序的方法详解

字体大小 | |
[开发(php) 所属分类 开发(php) | 发布者 店小二04 | 时间 | 作者 红领巾 ] 0人收藏点击收藏

本文实例讲述php实现基数排序的方法。分享给大家供大家参考,具体如下:

基数排序是根据关键字中各位的值,通过对排序的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}。

接下来,可以对十位数、百位数也按照这种方法进行排序,最后就能得到排序完成的序列。

<?php
/**基数排序**/
/*
* 获取第几位上的数字
*
*百位数 = 2345%1000/100
*/
function getN($num,$N){
$value = 10;
for($i=1;$i<$N;$i++){
$value = $value * 10;
}
$M = (int)(($num % $value /($value/10)));
return $M;
}
/*
*/
function paixu($arr)
{
$flag = 1;//该次位数上是否全为0标志位,全为0 flag=0
for($M=1;$flag!=0;$M++)
{
$flag = 0;
if($M > 1){
$m = 0;
for($j=0;$j<10;$j++){
for($k=0;$k<count($b[$j]);$k++){
if($b[$j][$k]!=0)
$arr[$m++] = $b[$j][$k];//将容器中的数按序取出,进行下一次排序
}
}
$b = array();//再给b附新值前要清空数组中原有的数据
}
for($i=0;$i<count($arr);$i++)
{
$thisNum = getN($arr[$i],$M);
if($thisNum!=0) $flag = 1;
$b[$thisNum][] = $arr[$i];//将数组中的数放入容器中
}
}
print_r($arr);
//var_dump($b);
}
/**基数排序**结束**/
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 )

基数排序还可以应用在查找重复数,查找间隔数等方面

代码不重要(我的代码仍需改进),思路是关键

PS:这里再为大家推荐一款关于排序的演示工具供大家参考:

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:
http://tools.jb51.net/aideddesign/paixu_ys

更多关于PHP相关内容感兴趣的读者可查看本站专题:《php排序算法总结》、《PHP数据结构与算法教程》、《php程序设计算法总结》、《PHP数组(Array)操作技巧大全》、《php字符串(string)用法总结》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》

希望本文所述对大家PHP程序设计有所帮助。

本文开发(php)相关术语:php代码审计工具 php开发工程师 移动开发者大会 移动互联网开发 web开发工程师 软件开发流程 软件开发工程师

主题: PHP算法数据结构数据
tags: gt,排序,PHP,arr,lt,flag,value,基数,php,个位数,算法
分页:12
转载请注明
本文标题:PHP实现基数排序的方法详解
本站链接:http://www.codesec.net/view/569995.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 开发(php) | 评论(0) | 阅读(79)