Detailed Explanation of Cardinal Sorting of Radix Sort Example of PHP Sorting Algorithm

In this paper, the cardinality sort (Radix Sort) of PHP sort algorithm is described as an example. Share it for your reference, as follows:

Cardinal sorting is not mentioned in Dahua Data Structure, but in order to make up the eight sorting algorithms, I learned this sorting algorithm through the network and shared it with everyone.

Basic ideas:

Cardinal sort (radix sort) belongs to "distributed sort" (distribution sort), Also known as "barrel method" (bucket sort) or bin sort, As its name implies, it assigns the elements to be sorted to some "buckets" through some information of key values, so as to achieve the sorting function. Radix sorting method belongs to stable sorting, and its time complexity is O (nlog (r) m), where r is the radix adopted and m is the heap number. In some cases, the efficiency of radix sorting method is higher than other stable sorting methods.

In fact, I can't sum up this idea either. Let's illustrate it with examples:

Basic solution:

PS: We use LSD (lowest bit first) and MSD (highest bit first) in the base ranking introduced here. Let's go to Baidu 1 to find out the similarities and differences between them.

Suppose we have the following numbers now:

2 343 342 1 128 43 4249 814 687 654 3

We use cardinality sorting to sort them from small to large.

Step 1, first, according to the single digit values, assign the values to buckets numbered 0 to 9 when visiting them (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

Step 2, then re-concatenate the values in these barrels into the following sequence:

1 2 342 343 43 3 814 654 687 128 4249

Step 3, according to the 10-digit values, assign them to buckets numbered 0 through 9 when visiting them (from front to back, the following steps are the same):

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

Step 4, then re-concatenate the values in these barrels into the following sequence:

1 2 3 814 128 342 343 43 4249 654 687

Step 5, according to the hundred digits, assign the values to buckets numbered 0 through 9 when visiting them (from front to back, the following steps are the same):

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

Step 6, then re-concatenate the values in these barrels into the following sequence:

1 2 3 43 128 4249 342 343 654 687 814

. . . . . . Everyone should have left the next steps. In fact, by the time of step 6, there are 4249 left out of order.

From the above steps, many steps are the same, so it must be a loop. We only need to control individual bits, 10 bits, 100 bits,,,,.

Let's look at the code.

Algorithm implementation:

// Commutative function 
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
// Gets the maximum number in the array 
// Just like the example above 1 If we finally stop the algorithm, it is only to look at the maximum value in the array: 4249 Its number of digits is the number of cycles 
function getMax(array $arr){
  $max = 0;
  $length = count($arr);
  for($i = 0;$i < $length;$i ++){
    if($max < $arr[$i]){
      $max = $arr[$i];
    }
  }
  return $max;
}
// Get the maximum number of digits , The maximum number of digits is the number of times we allocate buckets 
function getLoopTimes($maxNum){
  $count = 1;
  $temp = floor($maxNum / 10);
  while($temp != 0){
    $count ++;
    $temp = floor($temp / 10);
  }
  return $count;
}
/**
 * @param array $arr  Array to be sorted 
 * @param $loop  How many loops are identified 
 *  This function only completes a certain 1 Bits (bits or 10 Bits) 
 */
function R_Sort(array &$arr,$loop){
  // Bucket array, which in strongly typed languages should be declared as [10][count($arr)]
  // No. 1 1 Dimension  0-9 10 Number 
  // No. 1 2 Dimension is defined in this way because it is possible to sort all the numbers in the array. 1 The only thing in the position is 1 Like, so it's all crowded in 1 It's in a bucket 
  $tempArr = array();
  $count = count($arr);
  // Initialization $tempArr Array 
  for($i = 0;$i < 10;$i ++){
    $tempArr[$i] = array();
  }
  // Bucket-seeking index Divisor of 
  // Such as 798 Single-bit bucket index=(798/1)%10=8
  //10 Bucket index=(798/10)%10=9
  // Hundred bucket index=(798/100)%10=7
  //$tempNum Is in the above formula 1 , 10 , 100
  $tempNum = (int)pow(10, $loop - 1);
  for($i = 0;$i < $count;$i ++){
    // Find a number in a certain place 
    $row_index = ($arr[$i] / $tempNum) % 10;
    for($j = 0;$j < $count;$j ++){
      if(@$tempArr[$row_index][$j] == NULL){
        $tempArr[$row_index][$j] = $arr[$i];   // Bucket entry 
        break;
      }
    }
  }
  // Restore back to the original array 
  $k = 0;
  for($i = 0;$i < 10;$i ++){
    for($j = 0;$j < $count;$j ++){
      if(@$tempArr[$i][$j] != NULL){
        $arr[$k ++] = $tempArr[$i][$j];  // Out of the barrel 
        $tempArr[$i][$j] = NULL;  // Avoid polluting the data in the next cycle 
      }
    }
  }
}
// The main function that is finally called 
function RadixSort(array &$arr){
  $max = getMax($arr);
  $loop = getLoopTimes($max);
  // To each 1 Bit for bucket allocation ( 1  Represents a single bit, $loop  Represents the highest bit) 
  for($i = 1;$i <= $loop;$i ++){
    R_Sort($arr,$i);
  }
}

Invoke algorithm:

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

Run 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, I wrote these codes quite a long time ago. Today, when I was writing a blog, I found that the bucket is actually a queue, so the above R_Sort() The function is complicated, so we use array_push() And array_shift() To override this method (of course, to simulate queues, use the splqueue Is the most appropriate, I don't need it here for simplicity):

function R_Sort(array &$arr,$loop){
  $tempArr = array();
  $count = count($arr);
  for($i = 0;$i < 10;$i ++){
    $tempArr[$i] = array();
  }
  // Bucket-seeking index Divisor of 
  // Such as 798 Single-bit bucket index=(798/1)%10=8
  //10 Bucket index=(798/10)%10=9
  // Hundred bucket index=(798/100)%10=7
  //$tempNum Is in the above formula 1 , 10 , 100
  $tempNum = (int)pow(10, $loop - 1);
  for($i = 0;$i < $count;$i ++){
    // Find a number in a certain place 
    $row_index = ($arr[$i] / $tempNum) % 10;
    // Bucket entry 
    array_push($tempArr[$row_index],$arr[$i]);
  }
  // Restore back to the original array 
  $k = 0;
  for($i = 0;$i < 10;$i ++){
    // Out of the barrel 
    while(count($tempArr[$i]) > 0){
      $arr[$k ++] = array_shift($tempArr[$i]);
    }
  }
}

Cardinal sorting is a stable sorting method, and its time complexity is O (nlog (r) m), where r is the adopted cardinal and m is the number of heaps.

Ok, the cardinal sorting has been introduced to everyone here. The summary of this algorithm is mainly through looking at the data on the Internet, so the original author is no longer given.

PS: Here we recommend another demonstration tool about sorting for your reference:

Online animation demonstrates insert/select/bubble/merge/hill/quick sort algorithm process tool:
http://tools.ofstack.com/aideddesign/paixu_ys

For more readers interested in PHP related contents, please check the special topics of this site: Summary of php Sorting Algorithm, Tutorial of PHP Data Structure and Algorithm, Summary of php Programming Algorithm, Summary of php String (string) Usage, Encyclopedia of PHP Array (Array) Operation Skills, Summary of PHP Common Traversal Algorithms and Skills and Summary of PHP Mathematical Operation Skills

I hope this paper is helpful to everyone's PHP programming.