Home > Article > Backend Development > Detailed explanation of the steps to use PHP radix sort

Detailed explanation of the steps to use PHP radix sort

php中世界最好的语言Original: 2018-05-16 15:12:501770browse

This time I will bring you a detailed explanation of the steps for using PHP radix sort. What are the precautions for using PHP radix sort? . The following is a practical case, let's take a look.

Basic idea:

Radix sort (radix sort) belongs to "distribution sort" (distribution sort), also known as "bucket method" "(bucket sort) or bin sort, as the name suggests, it allocates the elements to be sorted into certain "buckets" through part of the key value information to achieve the sorting effect. The radix sort method is a stable sort. , its time complexity is O (nlog(r)m), where r is the radix taken, and m is the number of heaps. At some times, the radix sorting method is more efficient than other stability sorting methods.

In fact, I can’t summarize this idea. Let’s illustrate it through examples:

Basic solution:

PS: The radix sorting we introduce here uses LSD (lowest digit first), and of course MSD (highest digit first). Let’s go to Baidu to find out the similarities and differences between them.

Suppose now we have the following numbers:

2 343 342 1 128 43 4249 814 687 654 3

We use radix sort to sort them Sort from smallest to largest.

The first step is to first assign them to buckets numbered 0 to 9 according to the single-digit values when visiting the values (visiting from front to back, the following steps are the same):

0 :
1 : 1
2 : 2 342
3 : 343 43 3
4 : 814 654
5 :
6 :
7 : 687
8 : 128
9 : 4249

The second step is to reconnect the values in these buckets to become the following sequence:

1 2 342 343 43 3 814 654 687 128 4249

The third step, according to the ten-digit value, when visiting the value (visiting from front to back, the following steps are the same) Assigned to buckets numbered 0 to 9:

0 : 1 2 3
1 : 814
2 : 128
3 :
4 : 342 343 43 4249
5 : 654
6 :
7 :
8 : 687
9 :

The fourth step is to add the values in these buckets Reconnect them in series to form the following sequence:

1 2 3 814 128 342 343 43 4249 654 687

The fifth step is, based on the hundreds digit value, When visiting the values (visiting from front to back, the following steps are the same), assign them to buckets numbered 0 to 9:

0 : 1 2 3 43
1 : 128
2 : 4249
3 : 342 343
4 :
5 :
6 : 654 687
7 :
8 : 814
9 :

The sixth step is to reconnect the values in these buckets to form the following sequence:

1 2 3 43 128 4249 342 343 654 687 814

. . . . . . Everyone should be able to take the next steps. In fact, by the time we reach the sixth step, there are only 4249 left that have not been sorted.

Judging from the above steps, many steps are the same, so it must be a cycle. We only need to control the ones, tens, hundreds,,,,.

Let’s look at the code.

Algorithm implementation:

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

Calling algorithm:

$arr = array(2, 343, 342, 1, 128, 43, 4249, 814, 687, 654, 3);
RadixSort($arr);
var_dump($arr);

Running results:

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

In fact, these I wrote the code a long time ago. Today when I was blogging, I discovered that a bucket is actually a queue, so the R_Sort() function above is complicated. We use array_push() And <a href="http://www.php.cn/wiki/1008.html" target="_blank">array_shift</a>() to rewrite this method (of course, if you want to simulate a queue, it is most appropriate to use the splqueue provided by SPL, here for simplicity I won’t use it):

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

The radix sorting method is a stable sorting method, and its time complexity is O (nlog(r)m), where r is the radix taken. , and m is the number of heaps.

I believe you have mastered the method after reading the case in this article. For more exciting information, please pay attention to other related articles on the php Chinese website!

Detailed explanation of the steps to use PHP radix sort

Related articles