An explanation of how to implement radix sorting in PHP

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

PS: Here is another article about Sorting demonstration tools for your reference:

Online animation demonstration of insertion/selection/bubble/merge/Hill/quick sort algorithm process tools:
http://tools.jb51.net/aideddesign/paixu_ys

Articles you may be interested in:

PHP is based on reflection Explanation of the method of realizing automatic dependency injection by mechanism

##While PHP is in progress-detailed explanation of variables and explanation of dynamic string insertion of variables

Detailed explanation of using Telegram’s interface to implement free message notification function in PHP

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