基数排序:是一种非比较整数排序算法。
基数排序的基本原理是根据每个数字对整数进行分组。在分组的过程中，位数不足的数据用零填充。
基数排序按分组位数的顺序可分为LSD基数排序和MSD基数排序。
LSD基数排序是按照从低到高的顺序分组排序。例如:第一组是10，1，2，3，4，5，6，7，8，9，10后的1，2，3，4，5，6，7，8，9。
MSD基数排序是从高阶到低阶的分组排序。例如:第一组是1，10，2，3，4，5，6，7，8，9，10后的1，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
好了，这里先讨论基数排序的效率。接下来，是时候进入我们的核心问题了——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; }}
以上是基数排序中LSD模式的基本介绍。
本文来自胸大无脑是一种心态投稿，不代表舒华文档立场，如若转载，请注明出处：https://www.chinashuhua.cn/24/604596.html
微信扫一扫 
