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为堆数。

好了,到这里基数排序就已经给大家介绍完了。这个算法的总结主要是通过看网上的资料,所以就不再给出原作者了。

PS:这里再为大家推荐一款关于排序的演示工具供大家参考:

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:
http://tools.jb51.net/aideddesign/paixu_ys

更多关于PHP相关内容感兴趣的读者可查看本站专题:《php排序算法总结》、《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》

希望本文所述对大家PHP程序设计有所帮助。

您可能感兴趣的文章:

  • PHP排序算法系列之归并排序详解
  • php 归并排序 数组交集
  • 详解PHP归并排序的实现
  • PHP排序算法之快速排序(Quick Sort)及其优化算法详解
  • PHP排序算法之堆排序(Heap Sort)实例详解
  • PHP排序算法之希尔排序(Shell Sort)实例分析
  • PHP排序算法之直接插入排序(Straight Insertion Sort)实例分析
  • PHP排序算法之简单选择排序(Simple Selection Sort)实例分析
  • PHP排序算法之冒泡排序(Bubble Sort)实现方法详解
  • PHP排序算法之归并排序(Merging Sort)实例详解
(0)

相关推荐

  • 详解PHP归并排序的实现

    归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表.归并排序的一个缺点是它需要存储器有另一个大小等于数据项数目的数组.如果初始数组几乎占满整个存储器,那么归并排序将不能工作,但是如果有足够的空间,归并排序会是一个很好的选择. 假设待排序的序列: 4 3 7 9 2 8 6 先说思路,归并排序的中心思想是将两个已经排序好的序列,合并成一个排序的序列. 上面的序列可以分成: 4 3 7 9 和 2  8  6 这两个序列,然后对这两个序列分别排序:结果为: 设置为序列A,与序列

  • PHP排序算法之冒泡排序(Bubble Sort)实现方法详解

    本文实例讲述了PHP排序算法之冒泡排序(Bubble Sort)实现方法.分享给大家供大家参考,具体如下: 基本思想: 冒泡排序是一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止. 最简单排序实现: 我们先来看看在没有学习各种排序方法前经常使用的排序方法(至少我是这样....): //这里使用了类型提示(type hint) array,不熟悉或者不习惯的同学大可去掉,不影响运算结果 function MySort(array &$arr){ $le

  • PHP排序算法之简单选择排序(Simple Selection Sort)实例分析

    本文实例讲述了PHP排序算法之简单选择排序(Simple Selection Sort).分享给大家供大家参考,具体如下: 基本思想: 通过 n - i 次关键字间的比较,从 n - i + 1 个记录中选出关键字最小的记录,并和第 i (1 <= i <= n) 个记录交换,执行n-1趟 后就完成了记录序列的排序. 算法实现: <?php //简单选择排序 //交换函数 function swap(array &$arr,$a,$b){ $temp = $arr[$a]; $a

  • PHP排序算法之直接插入排序(Straight Insertion Sort)实例分析

    本文实例讲述了PHP排序算法之直接插入排序(Straight Insertion Sort).分享给大家供大家参考,具体如下: 算法引入: 在这里我们依然使用<大话数据结构>里面的一个例子: 扑克牌是我们几乎每个人都玩过的游戏.平时我们开始的时候一般都是一个人发牌,其他人都是一边摸牌,一边理牌,假如你摸上的第一张牌是 5,第二张牌是 3,自然而然的我们把 3 插到 5 的前面:第三张牌是 4,查到 3 和 5 的中间:第四张牌是 6,放到 5 的后面:第五张牌是 2,插到 3 的前面:--.最

  • PHP排序算法之希尔排序(Shell Sort)实例分析

    本文实例讲述了PHP排序算法之希尔排序(Shell Sort).分享给大家供大家参考,具体如下: 基本思想: 希尔排序是指记录按下标的一定增量分组,对每一组使用 直接插入排序 ,随着增量逐渐减少,每组包含的关键字越来越多,当增量减少至 1 时,整个序列恰好被分成一组,算法便终止. 操作步骤: 先取一个小于 n(序列记录个数) 的整数 d1 作为第一个增量,把文件的全部记录分组.所有距离为 d1 的倍数的记录放在同一个组中.先在各组内进行 直接插入排序:然后,取第二个增量 d2 < d1 重复上述

  • php 归并排序 数组交集

    复制代码 代码如下: $a=array('1','2','3','4','22'); $b=array('1','3','4','11','22','23'); f($a, $b, 5, 6, $t); print_r($t); function f(&$a, &$b, $n, $m, &$t){ $i=0;$j=0; while($i<$n && $j<$m){ if($a[$i]==$b[$j]){ echo $a[$i]." "

  • PHP排序算法系列之归并排序详解

    归并排序 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 归并过程 归并排序的核心就是如何将两个有序序列进行合并,假定有两个有序数组,比较两个有序数组的首个元素,谁小就取谁,并将该元素放入第三个数组中,取了之后在相应的数组中将删除此元素,依次类推,当取到一个数组已

  • PHP排序算法之归并排序(Merging Sort)实例详解

    本文实例讲述了PHP排序算法之归并排序(Merging Sort).分享给大家供大家参考,具体如下: 基本思想: 归并排序:就是利用归并(合并)的思想实现的排序方法.它的原理是假设初始序列含有 n 个元素,则可以看成是 n 个有序的子序列,每个子序列的长度为 1,然后两两归并,得到 ⌈ n / 2⌉ (⌈ x ⌉ 表示不小于 x 的最小整数)个长度为 2 或 1 的有序序列:再两两归并,······,如此重复,直至得到一个长度为 n 的有序序列为止,这种排序方法就成为 2 路归并排序. 一.归并

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

    本文实例讲述了PHP排序算法之快速排序(Quick Sort)及其优化算法.分享给大家供大家参考,具体如下: 基本思想: 快速排序(Quicksort)是对冒泡排序的一种改进.他的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行快速排序,整个排序过程可以递归进行,以达到整个序列有序的目的. 基本算法步骤: 举个栗子: 假如现在待排序记录是: 6   2   7   3   8   9 第一步.创建变量 $low 指

  • PHP排序算法之堆排序(Heap Sort)实例详解

    本文实例讲述了PHP排序算法之堆排序(Heap Sort).分享给大家供大家参考,具体如下: 算法引进: 在这里我直接引用<大话数据结构>里面的开头: 在前面讲到 简单选择排序 ,它在待排序的 n 个记录中选择一个最小的记录需要比较 n - 1 次,本来这也可以理解,查找第一个数据需要比较这么多次是正常的,否则如何知道他是最小的记录. 可惜的是,这样的操作并没有把每一趟的比较结果保存下来,在后一趟的比较重,有许多比较在前一趟已经做过了,但由于前一趟排序时未保存这些比较结果,所以后一趟排序时又重

随机推荐