Radix Sort of PHP sorting algorithm

This article mainly introduces the Radix Sort of the PHP sorting algorithm. It analyzes the principles, implementation methods and related usage skills of the PHP radix sorting algorithm in detail with examples. Friends in need can refer to it

The example in this article describes the radix sort (Radix Sort) of the PHP sorting algorithm. I share it with you for your reference. The details are as follows:

Cardinal sorting is not mentioned in "Dahua Data Structure", but in order to collect the eight major sorting algorithms, I learned this sorting algorithm through the Internet and gave it to Share it with everyone.

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 result:

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

Actually, I wrote these codes quite a while ago, and I am blogging today I discovered that the bucket is actually a queue, so the above

R_Sort() function is complicated. We use array_push() and array_shift() to rewrite it. This method (of course, if you want to simulate a queue, it is most appropriate to use the splqueue provided by SPL, but I will not use it here for simplicity):

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.

Related recommendations:

PHP sorting algorithm Quick Sort (Quick Sort) and its optimization

PHP sorting algorithm Merge Sort ( Merging Sort)

PHP sorting algorithm Bubble Sort

The above is the detailed content of Radix Sort of PHP sorting algorithm. For more information, please follow other related articles on the PHP Chinese website!