首页 / 算法 / PHP排序算法之基数排序(RadixSort

PHP排序算法之基数排序(RadixSort

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了PHP排序算法之基数排序(RadixSort，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5126字，纯文字阅读大概需要8分钟。

内容图文

这篇文章主要介绍了PHP排序算法之基数排序(Radix Sort),结合实例形式详细分析了php基数排序算法的原理、实现方法与相关使用技巧,需要的朋友可以参考下

本文实例讲述了PHP排序算法之基数排序(Radix Sort)。分享给大家供大家参考，具体如下：

基数排序在《大话数据结构》中并未讲到，但是为了凑齐八大排序算法，我自己通过网络学习了这个排序算法，并给大家分享出来。

基本思想：

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

其实这个思想我也没法总结出来，下面通过例子来说明吧：

基本解法：

PS：在这里我们介绍的基数排序我们采用 LSD（最低位优先），当然还有 MSD（最高位优先），大家自己去百度一下他们之间的异同吧。

假如现在我们有以下这么一些数：

2 343 342 1 128 43 4249 814 687 654 3

我们使用基数排序将他们从小到大排序。

第一步、首先根据个位数的数值，在走访数值（从前到后走访，后面步骤相同）时将它们分配至编号0到9的桶子中：

0 :
1 : 1
2 : 2 342
3 : 343 43 3
4 : 814 654
5 :
6 :
7 : 687
8 : 128
9 : 4249

第二步、接下来将这些桶子中的数值重新串接起来，成为以下的数列：

1 2 342 343 43 3 814 654 687 128 4249

第三步、根据十位数的数值，在走访数值（从前到后走访，后面步骤相同）时将它们分配至编号0到9的桶子中：

0 : 1 2 3
1 : 814
2 : 128
3 :
4 : 342 343 43 4249
5 : 654
6 :
7 :
8 : 687
9 :

第四步、接下来将这些桶子中的数值重新串接起来，成为以下的数列：

1 2 3 814 128 342 343 43 4249 654 687

第五步、根据百位数的数值，在走访数值（从前到后走访，后面步骤相同）时将它们分配至编号0到9的桶子中：

0 : 1 2 3 43
1 : 128
2 : 4249
3 : 342 343
4 :
5 :
6 : 654 687
7 :
8 : 814
9 :

第六步、接下来将这些桶子中的数值重新串接起来，成为以下的数列：

1 2 3 43 128 4249 342 343 654 687 814

。。。。。。后面的步骤大家应该都会走了吧。其实到了第六步的时候就剩 4249 没有排好序了。

从上面的步骤来看，很多的步骤都是相同的，因此肯定是个循环了，我们只需要控制个位、十位、百位、、、、就好了。

还是看代码吧。

算法实现：

//交换函数
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//获取数组中的最大数
//就像上面的例子一样，我们最终是否停止算法不过就是看数组中的最大值：4249，它的位数就是循环的次数
function getMax(array $arr){
  $max = 0;
  $length = count($arr);
  for($i = 0;$i < $length;$i ++){
    if($max < $arr[$i]){
      $max = $arr[$i];
    }
  }
  return $max;
}
//获取最大数的位数,最大值的位数就是我们分配桶的次数
function getLoopTimes($maxNum){
  $count = 1;
  $temp = floor($maxNum / 10);
  while($temp != 0){
    $count ++;
    $temp = floor($temp / 10);
  }
  return $count;
}
/**
 * @param array $arr 待排序数组
 * @param $loop 第几次循环标识
 * 该函数只是完成某一位（个位或十位）上的桶排序
 */
function R_Sort(array &$arr,$loop){
  //桶数组，在强类型语言中，这个数组应该声明为[10][count($arr)]
  //第一维是 0-9 十个数
  //第二维这样定义是因为有可能待排序的数组中的所有数的某一位上的只是一样的，这样就全挤在一个桶里面了
  $tempArr = array();
  $count = count($arr);
  //初始化$tempArr数组
  for($i = 0;$i < 10;$i ++){
    $tempArr[$i] = array();
  }
  //求桶的index的除数
  //如798个位桶index=(798/1)%10=8
  //十位桶index=(798/10)%10=9
  //百位桶index=(798/100)%10=7
  //$tempNum为上式中的1、10、100
  $tempNum = (int)pow(10, $loop - 1);
  for($i = 0;$i < $count;$i ++){
    //求出某位上的数字
    $row_index = ($arr[$i] / $tempNum) % 10;
    for($j = 0;$j < $count;$j ++){
      if(@$tempArr[$row_index][$j] == NULL){
        $tempArr[$row_index][$j] = $arr[$i];   //入桶
        break;
      }
    }
  }
  //还原回原数组中
  $k = 0;
  for($i = 0;$i < 10;$i ++){
    for($j = 0;$j < $count;$j ++){
      if(@$tempArr[$i][$j] != NULL){
        $arr[$k ++] = $tempArr[$i][$j];  //出桶
        $tempArr[$i][$j] = NULL;  //避免下次循环的时候污染数据
      }
    }
  }
}
//最终调用的主函数
function RadixSort(array &$arr){
  $max = getMax($arr);
  $loop = getLoopTimes($max);
  //对每一位进行桶分配（1 表示个位，$loop 表示最高位）
  for($i = 1;$i <= $loop;$i ++){
    R_Sort($arr,$i);
  }
}

调用算法：

$arr = array(2, 343, 342, 1, 128, 43, 4249, 814, 687, 654, 3);
RadixSort($arr);
var_dump($arr);

运行结果：

array(11) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(43)
 [4]=>
 int(128)
 [5]=>
 int(342)
 [6]=>
 int(343)
 [7]=>
 int(654)
 [8]=>
 int(687)
 [9]=>
 int(814)
 [10]=>
 int(4249)
}

其实这些代码我是在挺早之前写的，今天在写博客的时候发现，其实桶就是一个队列，所以上面的 R_Sort()函数复杂了，我们使用 array_push() 和 array_shift() 来重写该方法（当然，要模拟队列的话，用 SPL 提供的 splqueue 是最为恰当的，在这里为了简便我就不用了）：

function R_Sort(array &$arr,$loop){
  $tempArr = array();
  $count = count($arr);
  for($i = 0;$i < 10;$i ++){
    $tempArr[$i] = array();
  }
  //求桶的index的除数
  //如798个位桶index=(798/1)%10=8
  //十位桶index=(798/10)%10=9
  //百位桶index=(798/100)%10=7
  //$tempNum为上式中的1、10、100
  $tempNum = (int)pow(10, $loop - 1);
  for($i = 0;$i < $count;$i ++){
    //求出某位上的数字
    $row_index = ($arr[$i] / $tempNum) % 10;
    //入桶
    array_push($tempArr[$row_index],$arr[$i]);
  }
  //还原回原数组中
  $k = 0;
  for($i = 0;$i < 10;$i ++){
    //出桶
    while(count($tempArr[$i]) > 0){
      $arr[$k ++] = array_shift($tempArr[$i]);
    }
  }
}

基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数。

相关推荐：

PHP排序算法之快速排序(Quick Sort)及其优化

PHP排序算法之归并排序(Merging Sort)

PHP排序算法之冒泡排序(Bubble Sort)

以上就是PHP排序算法之基数排序(Radix Sort的详细内容，更多请关注Gxl网其它相关文章！

内容总结

以上是互联网集市为您收集整理的PHP排序算法之基数排序(RadixSort全部内容，希望文章能够帮你解决PHP排序算法之基数排序(RadixSort所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/137407.html

来源：【匿名】