PHP radix sort method

This article mainly introduces the method of implementing radix sorting in PHP, and analyzes the principles, implementation methods and related operating techniques of radix sorting in the form of examples. Friends in need can refer to the following

The examples in this article describe PHP How to implement radix sort. Share it with everyone for your reference, the details are as follows:

Cardinal sorting is based on the value of each bit in the keyword, and the sorting is achieved by performing several passes of "distribution" and "collection" on the sorted N elements.

Want to use a specific example to show how radix sorting is performed.

Suppose an initial sequence is: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}.

We know that for any Arabic number, the base of each digit is represented by 0~9.

So we might as well regard 0~9 as 10 buckets.

We first classify according to the single-digit numbers of the sequence and divide them into specified buckets. For example: R[0] = 50, the single digit is 0, store this number in the bucket numbered 0.

After classification, we take out all the numbers from each bucket in order from number 0 to number 9.

At this time, the obtained sequence is a sequence with an increasing trend in single digits.

Sort by single digits: {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}.

Next, you can sort the tens and hundreds digits in this way, and finally you can get the sorted sequence.

<?php
/**基数排序**/
/*
* 获取第几位上的数字
*
*百位数 = 2345%1000/100
*/
function getN($num,$N){
  $value = 10;
  for($i=1;$i<$N;$i++){
    $value = $value * 10;
  }
  $M = (int)(($num % $value /($value/10)));
  return $M;
}
/*
*/
function paixu($arr)
{
  $flag = 1;//该次位数上是否全为0标志位，全为0 flag=0
  for($M=1;$flag!=0;$M++)
  {
    $flag = 0;
    if($M > 1){
      $m = 0;
      for($j=0;$j<10;$j++){
        for($k=0;$k<count($b[$j]);$k++){
          if($b[$j][$k]!=0)
          $arr[$m++] = $b[$j][$k];//将容器中的数按序取出，进行下一次排序
        }
      }
      $b = array();//再给b附新值前要清空数组中原有的数据
    }
    for($i=0;$i<count($arr);$i++)
    {
      $thisNum = getN($arr[$i],$M);
      if($thisNum!=0) $flag = 1;
      $b[$thisNum][] = $arr[$i];//将数组中的数放入容器中
    }
  }
  print_r($arr);
  //var_dump($b);
}
/**基数排序**结束**/
paixu(array(65,3,45,6,7,8,31,100,1000,1234))
?>

Run result:

Copy code The code is as follows:

Array ( [0] => 3 [1] => 6 [2] => 7 [3] => 8 [4] => 31 [5] => 45 [6 ] => 65 [7] => 100 [8] => 1000 [9] => 1234 )

##Radix sort can also be used to find duplicates Number, search interval number, etc.

The code is not important (my code still needs to be improved), the idea is the key

Related recommendations:

PHP Summary of sorting algorithm implementation

PHP sorting algorithm Heap Sort

PHP sorting algorithm Radix Sort

##

The above is the detailed content of PHP radix sort method. For more information, please follow other related articles on the PHP Chinese website!