Detailed explanation of how to implement radix sorting in PHP_php skills

This article mainly introduces the method of PHP to implement radix sorting, and analyzes the principles, implementation methods and related PHP operation skills of radix sorting in the form of examples. The examples in this article describe PHPMethod to implement radix sorting. Share it with everyone for your reference, let’s take a look!

Radix sorting is based on the value of each bit in the keyword, and is sorted 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 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))
?>

Running results:

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 duplicate numbers, find In terms of the number of intervals, etc., the code is actually not important (my code still needs to be improved), the idea is the key

Related recommendations:

##PHP sorting implementation

PHP sorting two-dimensional array alphabetical sorting implementation code

php sorting algorithm ( Bubble sort, quick sort)_PHP tutorial

The above is the detailed content of Detailed explanation of how to implement radix sorting in PHP_php skills. For more information, please follow other related articles on the PHP Chinese website!