基数排序
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法
方法：最高位优先MSD、最低位优先LSD
思想：最低位优先LSD方案
1、 将待排数字根据个位上的数字进行排序
2、 将待第一步排序结果再按照十位上数字进行排序
3、 按照位数从低到高依次排序
示例：
$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
function getIndex($num, $index) {
$val = pow(10, $index - 1);
return ($num / $val) % 10;
}
function radix_sort($arr,$max_len) {
for($i = 1; $i <= $max_len; $i++) {
$temp = array_fill(0, 10, array());//填充桶
foreach ($arr as $v) {
echo $index = getIndex($v, $i);
echo '#';
$temp[$index][] = $v;
}
$arr = array();
echo "\n第".$i. '次排序之后:';
foreach ($temp as $v) {
for($j =0 ;$j < count($v); $j++) {
echo $v[$j] ."," ;
$arr[] = $v[$j];
}
}
echo "\n";
}
return $arr;
}
$arr = radix_sort($arr, 3);
print_r($arr);以上示例有一个问题，如果排序的数字是负数呢？
$arr = array(1,4,5,89,22,44,-5,33,-6,7,-82,332);
function getIndex($num, $index) {
$val = pow(10, $index - 1);
return 10+($num / $val) % 10;
}
function radix_sort($arr,$max_len) {
for($i = 1; $i <= $max_len; $i++) {
$temp = array_fill(0, 19, array());//填充桶，负数填充-9~0~9对应0~10~19
foreach ($arr as $v) {
echo $index = getIndex($v, $i);
echo '#';
$temp[$index][] = $v;
}
$arr = array();
echo "\n第".$i. '次排序之后:';
foreach ($temp as $v) {
for($j =0 ;$j < count($v); $j++) {
echo $v[$j] ."," ;
$arr[] = $v[$j];
}
}
echo "\n";
}
return $arr;
}
$arr = radix_sort($arr, 3);
print_r($arr);本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016年7月19日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读