PHP sorting algorithm series bucket sorting detailed explanation_php skills

This article mainly introduces the bucket sorting of the PHP sorting algorithm series to you in detail. It has a certain reference value. Interested friends can refer to it. I hope it can help everyone.

Bucket sort

Bucket sort, or so-called box sort, is a sorting algorithm that works by dividing arrays into a limited number of buckets . Each bucket is sorted individually (it may be possible to use another sorting algorithm or continue to use bucket sorting recursively). Bucket sort is an inductive result of pigeonhole sort. Bucket sort uses linear time (Θ(n)) when the values ​​in the array to be sorted are evenly distributed. But bucket sorting is not a comparison sorting, and it is not affected by the lower limit of O(n log n).

Principle

Set a quantitative array as an empty bucket.
Search the sequence and put the items into the corresponding bucket one by one.
Sort each bucket that is not empty.
Put items back into the original sequence from the bucket that is not empty.

Example

Assume the numbers to be sorted [6 2 4 1 5 9]

Prepare 10 empty buckets, the maximum Several empty buckets
[0 0 0 0 0 0 0 0 0 0] Empty bucket
[0 1 2 3 4 5 6 7 8 9] Bucket number (actually does not exist)

1. Take out numbers from the array to be sorted sequentially. First, 6 is taken out, and then 6 is put into bucket No. 6. The process is similar to this: empty bucket [array to be sorted [ 0 ] ] = array to be sorted [ 0 ]

[6 2 4 1 5 9] Array to be sorted
[0 0 0 0 0 0 6 0 0 0] Empty bucket
[0 1 2 3 4 5 6 7 8 9] Bucket number (actually does not exist)

2. Sequentially take out the next number from the array to be sorted. At this time, 2 is taken out, and put it into bucket No. 2, whichever number it is.

[6 2 4 1 5 9] Array to be sorted
[0 0 2 0 0 0 6 0 0 0] Empty bucket
[0 1 2 3 4 5 6 7 8 9] Bucket number (actually does not exist)

3,4,5,6 are omitted, the process is the same, after all are put into the bucket, it will become like this

[6 2 4 1 5 9] Array to be sorted
[0 1 2 0 4 5 6 0 0 9] Empty bucket
[0 1 2 3 4 5 6 7 8 9] Bucket number (actually does not exist)
0 means empty bucket, skip it, just take it out in order: 1 2 4 5 6 9

PHP code implementation

<?php
function bucket_sort($arr){
 $result=[];
 $length=count($arr);
 //入桶
 for($i=0,$max=$arr[$i];$i<$length;$i++){
  if ($max<$arr[$i]) {
   $max=$arr[$i];
  }
  $bucket[$arr[$i]]=[];
  array_push($bucket[$arr[$i]],$arr[$i]);
 }
 //出桶
 for($i=0;$i<=$max;$i++){
  if(!empty($bucket[$i])){
   $l=count($bucket[$i]);
   for ($j=0; $j <$l ; $j++) {
    $result[]=$bucket[$i][$j];
   }
  }
 }
 return $result;
}

Related recommendations:

Ovulation period calculation method Review and summary of PHP sorting algorithm

Review and summary of PHP sorting algorithm_PHP tutorial

php sorting algorithm?php sorting classic algorithm_PHP tutorial

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