个人中心
gpt4 book ai didi

PHP排序算法之基数排序(Radix Sort)实例详解

转载 作者：qq735679552 更新时间：2022-09-29 22:32:09 30 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章PHP排序算法之基数排序(Radix Sort)实例详解由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

本文实例讲述了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程序设计有所帮助.

最后此篇关于PHP排序算法之基数排序(Radix Sort)实例详解的文章就讲到这里了,如果你想了解更多关于PHP排序算法之基数排序(Radix Sort)实例详解的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

30 4 0
文章推荐： PHP实现Huffman编码/解码的示例代码
文章推荐： PHP排序算法之堆排序(Heap Sort)实例详解
文章推荐： Laravel模型间关系设置分表的方法示例
文章推荐： PHP排序算法之快速排序(Quick Sort)及其优化算法详解
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com