Detailed explanation of bucket sorting in PHP sorting algorithm series

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

Bucket sorting

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 from the bucket that is not empty back into the original sequence.

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. Take out the next number from the array to be sorted sequentially. 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;
}

The above is the entire content of this article. I hope it will be helpful to everyone's study. I also hope that everyone will support the php Chinese website.

Articles you may be interested in:

Detailed explanation of merge sort of PHP sorting algorithm series_php skills

Detailed explanation of direct selection sort in PHP sorting algorithm series

Detailed explanation of insertion sort in PHP sorting algorithm series

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