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

转载 作者：qq735679552 更新时间：2022-09-29 22:32:09 30 4

//交换函数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)}

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]);    }  }}

30 4 0

• sorting - 性能 : Sorting Slice vs Sorting Type (of Slice) with Sort implementation

  我在玩一些代码挑战时发现自定义排序(排序接口(interface)的实现)比仅针对 slice 的原始结构要快得多。这是为什么？将 slice 转换为类型是否会产生一些魔力(例如转换为指向结构的指针

• reactjs - 未找到规则 'simple-import-sort/sort' 的定义 simple-import-sort/sort

  我正在使用 simple-import-sort eslint 插件进行 react 。我想我的 .eslintrc.js是对的，但我无法使这个特定的插件工作。我在文件的第一行收到以下错误: 未找到规

• sorting - sort.Slice排序不正确

  Closed. This question is not reproducible or was caused by typos。它当前不接受答案。 想改善这个问题吗？更新问题，以便将其作为on-to

• golang 不能在 sort.Sort 的参数中使用类型作为类型 sort.Interface

  好的，所以我是 Go 的新手，我正在努力让自己熟悉按函数排序。我可能误解了什么，所以如果我错了请纠正我。 我正在尝试创建一个包含字段 key 和 value 的 Nodes 数组。我想创建一个自定义排

• sorting - `take n (sort xs)` ("sorted prefix") 问题的内存高效算法

  我想从惰性列表中取出 n 个最大的元素。 我听说在 Data.List.sort 中实现的合并排序是惰性的，它不会产生不必要的元素。就比较而言，这可能是正确的，但在内存使用方面肯定不是这样。下面的程序

• javascript - 两个回调作为 Array.sort() 的参数，而不是 Array.sort().sort()

  这个问题已经有答案了: Javascript sort function. Sort by First then by Second (10 个回答) 已关闭 3 年前。 我正在尝试返回已排序产品的列

• c++ - 成对 vector : first pair values are non-sorted and second pair values are sorted: how to find a sorted value when having the non-sorted one

  我有一个 vector 对，如下所示。第一对值未排序，第二对值已排序(从零开始)。我可能想通过实现 std::vector 和 std::pair 来存储数据。当我有第一对值(未排序)时，找到相应的第

• nstableview - swift 3 : Sort (formerly sort-in-place) array by sort descriptors

  直到现在(Swift 2.2)我一直愉快地使用来自 this answer 的代码- 它迅速，优雅，它像梦一样工作。 extension MutableCollectionType where Ind

• sorting - Golang Sort :does not implement sort. 接口(interface)(缺少 Len 方法)

  我在我的 Go 应用程序中实现排序界面时遇到问题。这是相关代码: type Group struct { Teams []*Team } type Team struct { Point

• sorting - table.sort 使用什么算法？

  我很好奇 Lua 的默认算法是什么 table.sort使用，只是因为它比我遇到的其他一些排序算法慢。我也很好奇 Lua 的 table.sort是在引擎中用 C 编写的，或者如果它在 Lua 中的库

• sorting - "partially sorted"的数学定义

  例如，插入排序被描述为部分排序数组的有效算法。但如何精确定义“部分排序”呢？ 最佳答案 这是一个只有少数元素不合适的数组。如果没有指定百分比或其他阈值，则部分排序和未排序之间没有严格的区别。 正式定义

• sorting - Thrust::sort 有多快以及最快的基数排序实现是什么

  我是 GPU 编程的新手。最近，我正在尝试根据一个教程实现gpu bvh构建算法:http://devblogs.nvidia.com/parallelforall/thinking-parallel

• sorting - Gnumeric Sort 函数

  有人可以指导我 Gnumeric 排序函数的详细说明(链接)吗？ Gnumeric 手册很简短并且没有示例。我无法通过搜索引擎找到任何合适的信息，甚至 Stackoverflow 上也只有六个不合适的

• Python sort and sorted -- 列表的列表如何精确排序？

  在 Python 中使用什么精确规则来对列表进行排序，其中元素是列表？这可以表示为“key”或“cmp”吗功能？问题来自于有两件事考虑:长度和它们位置的值。 sorted([ [ 0, 1, 2

• go - sort.Sort 不修改数组

  下面的代码应该创建一个整数数组 (a) 并对它进行排序，但是 sort.Sort 似乎没有修改变量。 package main import ( "fmt" "sort" ) type

• sorting - golang sort.Sort随机输出并且是错误的

  我有一个应用于结构的自定义排序函数。完整代码是 here on play.golang.org . type Stmt struct { Name string After []st

• 对python3 sort sorted 函数的应用详解

  python3 sorted取消了对cmp的支持。 python3 帮助文档： ?

• algorithm - Shellsort - 如果一个数组是 g-sorted 然后 h-sorted，数组仍然是 g-sorted

  以下是来自普林斯顿的 coursera 算法类(class)的练习。 如果一个数组既是 3 次排序又是 5 次排序，那么它是否也是 6 次、7 次、8 次、9 次和 10 次排序？我知道任何序列如果先

• algorithm - "A g-sorted array remains g-sorted even after h-sorting it"的含义是什么？

  当我看到上面的语句时，我正在阅读 shell-sorting。这意味着什么？它对我看待 shell 排序的方式有何不同？ PS:我不是在寻找声明的证据。 最佳答案 好吧，你可能暗示下一个排序阶段不会“

• mysql Sort aborted: Out of sort memory, consider increasing server sort buffer size的解决方法

  今天在检查mysql服务器的时候提示Sort aborted: Out of sort memory, consider increasing server sort buffer size，安装字