迹忆客 专注技术分享

当前位置:主页 > 学无止境 > 算法 >

排序算法学习之路——基数排序(LSD)

作者:迹忆 最近更新:2022/11/19 浏览次数:

基数排序(Radix Sort):是一种非比较型的整数排序算法。

基数排序的基本原理是,按照整数的每个位数分组。在分组过程中,对于不足位的数据用0补位。

基数排序按照对位数分组的顺序的不同,可以分为LSD基数排序和MSD基数排序。

LSD基数排序,是按照从低位到高位的顺序进行分组排序。例如:1,2,3,4,5,6,7,8,9,10第一次分组后为 10,1,2,3,4,5,6,7,8,9。

MSD基数排序,是按照从高位到低位的顺序进行分组排序。例如:1,2,3,4,5,6,7,8,9,10 第一次分组以后为 1,10,2,3,4,5,6,7,8,9。

上述两种方式不仅仅是对位数分组顺序不同,其实现原理也是不同的。这里我们只先介绍LSD基数排序。

首先我们看LSD基数排序是如何进行的

对于序列中的每个整数的每一位都可以看成是一个桶,而该位上的数字就可以认为是这个桶的键值。这句话应该怎么理解呢,我们来看这样的一个序列

170, 45, 75, 90, 802, 2, 24, 66

这是一个整数序列,我们知道,对于每个整数的每一位上的值肯定是介于0和9之间的。因此,要想对这个序列进行LSD排序,那就必须有10个桶。这10个桶的索引分别就是0——9这十个数。对于LSD基数排序来说,每一次分组过程就是将相应的整数放进相应的桶中。

拿第一次分组来说吧,对于每个整数要按照个位上的数进行分组。那么我们看170,其个位为0,所以说170应该放进0这个桶中。然后以此类推 45放在5这个桶中。

所以上述序列的第一次分组后,各个整数所在的桶如下

0: 170, 090
1: 空
2: 802, 002
3: 空
4: 024
5: 045, 075
6: 066
7–9: 空

然后再将这些数依次收集起来,第一次分组再组合以后的序列为

170, 90, 802, 2, 24, 45, 75, 66

接着就是针对十位上的数进行分组入桶,入桶的情况如下

0: 802, 002
1: 空
2: 024
3: 空
4: 045
5: 空
6: 066
7: 170, 075
8: 空
9: 090

再次整理起来以后为下面的序列

802, 2, 24, 45, 66, 170, 75, 90

最后再次进行第三次(百位上的数)分组入桶

0: 002, 024, 045, 066, 075, 090
1: 170
2–7: 空
8: 802
9: 空

整理起来以后,我们发现整个序列已经是有序的了

2, 24, 45, 66, 75, 90, 170, 802

整个LSD基数排序的过程就是这样的,当然不同的程序可以构造不同的存放数据的桶的形式。但是其原理是相同的。

LSD基数排序是一个快速的稳定排序算法。其时间复杂度可以表示为O(Kn)。其中n就是待排序序列的元素个数,K是数字的位数。对于这个K我们应该怎样理解这个需要为大家说明一下。有时候K可以看做是一个常数——对于上述例子,其中K就是3。因为在上面的例子中最大的数是802,该数有3位。因此,在这种情况下,基数排序要比任何比较型的排序算法的效率要高。因为在比较型的排序算法中,最优的排序算法的时间复杂度也是O(nlogn)。

但是在一般情况下,K并不能再被认为是个常数。那K应该是什么呢。这里我们以十进制的数为例。整数序列中的每个数是以10为底的数。不妨我们用b记为底数,即b=10。那如果整个整数序列中的最大数是N。那这就很容易看出,K= logbN。所以在一般情况下,基数排序的时间复杂度可以看做是O(n logbN)。在N非常大的情况下是不是基数排序的效率要低于比最优的比较型的排序算法(最优的比较型的排序算法的时间复杂度是O(nlogn))。现在让我们假设N <= nc ,这里c是一个常数。这种情况下基数排序的时间复杂度就变成了O(n logbn)。但是即使这样,也不能比复杂度是O(nlogn)的比较型排序算法更快。那如果我们使b的值变大呢?如果我们使得b的值为n的话,这样基数排序的时间复杂度是不是就变成了线性的了,即O(n)。也就是说,如果待排序的序列的数是以n为底的话,那序列中的数可以是1到nc 之间的数。其时间复杂度就是线性的。

好了,对于基数排序的效率问题,我们就先讨论到这里。接下来就该进入我们的核心问题——LSD基数排序代码的实现。

/**
 * 找到序列中最大位数
 */
function FindMaxBit($arr){
    /*
     * 首先查找序列中最大的数
     */
    $p = $arr[0];
    for($i=1;$i<count($arr);$i++){
        if($arr[$i]>=$p){
            $p = $arr[$i];
        }
    }
    //得到最大的数以后,计算出该数据有多少位
    $d = 1;
    while(floor($p/10)>0){
        $d++;
        $p = floor($p/10);
    }
    return $d;
}
function LSD_RadixSort(&$arr){
    //得到序列中最大位数
    $d = FindMaxBit($arr);
    $bucket = array();
    //初始化队列
    for($i=0;$i<10;$i++){
        $bucket[$i]=array('num'=>0,'val'=>array());
    }
    /*
     * 开始进行分配
     */
    $radix = 1;
    for($i=1;$i<=$d;$i++){
        for($j=0;$j<count($arr);$j++){
            $k = floor($arr[$j]/$radix)%10;
            $bucket[$k]['num']++;
            array_push($bucket[$k]['val'],$arr[$j]);
        }
        $arr = array();
        foreach ($bucket as $key => $val) {
            for ($j = 0; $j < $val['num']; $j ++) {
                $arr[] = $val['val'][$j];
            }
        }
        for($l=0;$l<10;$l++){
            $bucket[$l]=array('num'=>0,'val'=>array());
        }
        $radix *= 10;
    }
}
$arr = array(
    15,77,23,43,90,87,68,32,11,22,33,99,88,66,44,113,
    224,765,980,159,456,7,998,451,96,0,673,82,91,100
);
LSD_RadixSort($arr,0,count($arr)-1);
print_r($arr);

在上面的代码中,我是将实际的数据直接存放在桶中了。然后将桶中的数据按照顺序覆盖掉原队列中的数据。然后再次将被覆盖后的队列进行分组,依次进行下去。

当然还有一种方式就是,申请一个和原序列相同大小的队列(不妨成为临时队列),然后再申请一个用于作桶的数组。桶中只是存放原序列中的数在临时队列中的位置,然后将原序列中的数按照桶中的顺序放入临时队列中。然后将临时队列整个赋值给原序列。

二者虽然实现方式不同,但是其空间复杂度是相同的。下面我们看后者应该如何用代码实现。

function LSD_RadixSort(&$arr){
    //得到序列中最大位数
    $d = FindMaxBit($arr);
    $bucket = array();
    $temp = array();
    //初始化队列
    for($i=0;$i<10;$i++){
        $bucket[$i] = 0;
    }
    /*
     * 开始进行分配
     */
    $radix = 1;
    for($i=1;$i<=$d;$i++){
        for($j=0;$j<count($arr);$j++){
            $k = floor($arr[$j]/$radix)%10;
            $bucket[$k]++;
        }
        //在桶中调整原序列在临时队列中的位置
        for($j=1;$j<10;$j++){
            $bucket[$j] += $bucket[$j-1];
        }
        for($j=count($arr)-1;$j>=0;$j--){
            $k = floor($arr[$j]/$radix)%10;
            $temp[--$bucket[$k]] = $arr[$j];
        }
        /*
         * 将临时队列赋值给原序列
         */
        for($j=0;$j<count($temp);$j++){
            $arr[$j] = $temp[$j];
        }
        for($j=0;$j<10;$j++){
            $bucket[$j] = 0;
        }
        $radix *= 10;
    }
}

上述就是对基数排序的基本介绍。希望这些能对大家有所帮助。

转载请发邮件至 1244347461@qq.com 进行申请,经作者同意之后,转载请以链接形式注明出处

本文地址:

相关文章

全面了解归并排序算法及代码实现

发布时间:2021/08/19 浏览次数:275 分类:算法

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。这里拆分过程的代码可以分为两种方式:递归实现和非递归实现

排序算法学习之路——基数排序(MSD)

发布时间:2016/04/14 浏览次数:6071 分类:算法

MSD基数排序是从最高位开始对序列进行分组,到最低位为止。但是其实现过程是和LSD基数排序不同的,排序过程中需要用到递归函数。

常用排序算法的核心代码

发布时间:2016/04/13 浏览次数:292 分类:算法

主要对常用排序算法的核心代码的实现,代码都是使用PHP实现的。完整代码托管在github上

排序算法学习之路——冒泡排序

发布时间:2016/04/13 浏览次数:379 分类:算法

冒泡排序也是一种简单直观的排序算法。其思想是:它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有

排序算法学习之路——选择排序

发布时间:2016/04/12 浏览次数:424 分类:算法

选择排序是一种简单直观的排序算法。其基本思想是在未排序的序列中选择一个最大(或最小)元素放到末尾(注意:这里是未排序序列的末尾,可以认为是有序序列的起始位置)。

常用排序算法

发布时间:2016/04/12 浏览次数:1159 分类:算法

本篇给大家介绍几种常用的排序算法,其中包括:插入排序,快速排序,希尔排序,堆排序,归并排序等排序算法,以及每种排序算法的实现代码。

排序算法学习之路——堆排序

发布时间:2016/04/11 浏览次数:873 分类:算法

堆排序(Heapsort):是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节

排序算法学习之路——快速排序(非递归实现)

发布时间:2016/04/09 浏览次数:3340 分类:算法

在快速排序这篇文章中我们介绍了快速排序的原理和步骤,以及使用递归的方式实现了该算法。而且在上篇文章中我们还提到使用非递归的方式实现该算法,本篇我们就使用非递归的方

排序算法学习之路——快速排序

发布时间:2016/04/08 浏览次数:45216 分类:算法

快速排序是由东尼•霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比

扫一扫阅读全部技术教程

社交账号
  • https://www.github.com/onmpw
  • qq:1244347461

最新推荐

教程更新

热门标签

扫码一下
查看教程更方便