基数排序

基数排序(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);

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户2442861的专栏

c++ 11 新特性

赖勇浩(http://laiyonghao.com) 声明:本文源自 Danny Kalev 在 2011 年 6 月 21 日发表的《The Bigges...

1111
来自专栏诸葛青云的专栏

简述在C语言中, “字符”与“字符串”之间的区别

在C语言中,“字符”与“字符串”之间,是有区别的。这一篇文章中,我们将介绍一下,在C语言中的“字符”与“字符串”,它们之间的区别。

2143
来自专栏程序员叨叨叨

8.1 函数第 8 章 函数与程序设计

通过第 5 章到第 7 章的阅读,我们已经知道了怎么声明变量(第 5 章),怎么写表达式和语句(第 6 章),怎么将输入 \ 输出参数绑定到语义词(第 7 章)...

1012
来自专栏一英里广度一英寸深度的学习

三路快排算法-求中位数问题(4)

step1排列数组的时间复杂度是O(N),空间复杂度是O(1) step2 递归调用的复杂度O(logN)

2742
来自专栏Java帮帮-微信公众号-技术文章全总结

第二天 变量数据类型运算符【悟空教程】

1606
来自专栏诸葛青云的专栏

C语言陷阱「词法陷阱 之字符与字符串」

用单引号引起的一个字符实际上表示一个整数,该整数值为该字符在编译器采用的字符集中的序列值。所以,对于采用ASCLL字符集的编译器,'a'对应的整数值为97(十进...

1304
来自专栏怀英的自我修炼

Java漫谈6

今天这篇想聊聊数组。 在聊数组之前先聊个别的,如果想在Java中实现一个 数字-月份 转换,那我该怎么做呢?就比如数字1代表了一月份,数字2代表了二月份…数字1...

3679
来自专栏Java帮帮-微信公众号-技术文章全总结

09(02)总结final,多态,抽象类,接口

(4)抽象类的练习 A:猫狗案例练习 B:老师案例练习 C:学生案例练习 D:员工案例练习 /* A: 猫狗案例 具体事物:猫,狗 共性:姓名,...

4216
来自专栏Java帮帮-微信公众号-技术文章全总结

第十一天 面向对象-接口多态【悟空教程】

1594
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java提高二】三大特性-继承

【Java提高】三大特性-继承 在《Think in java》中有这样一句话:复用代码是Java众多引人注目的功能之一。但要想成为极具革命性的语言,仅仅能够...

3539

扫码关注云+社区

领取腾讯云代金券