This is the 20th day of my participation in the Genwen Challenge

Introduction to the instance

Mr. Wang’s cram school taught 5 children. Mr. Wang asked the 5 children to do a 10-point intelligence algorithm, and the 5 children got different scores: 7,5,7,8,7,5. Now you need to print out the five scores in ascending order.

First, we initialize an array score[] of length 11, with positions 0-10 corresponding to scores of 10.

So, we get an array like this:

score[0] =0;// No child has ever scored 0
score[1] =0;// No children scored 1 point
score[2] =0;// No child scored 2 points
score[3] =0;// No child scored 3 points
score[4] =0;// No child scored 4 points
score[5] =2;// There are 2 children who scored 5 points
score[6] =0;// No child scored 6 points
score[7] =3;// There are 3 children who scored 7 points
score[8] =1;// There is one child who scored 8 points
score[9] =0;// No child scored 9 points
score[10] =0;// No child scored 10 points
Copy the code

Finally, we simply iterate through the array sequentially, not printing positions for values 0, and printing fractions for values other than 0:

// score[0]~score[4
5.5 // Score [5]=2, there are 2 children who have 5 points
// score[6]=0
7.7.7 // Score [7]=3, there are 3 children who have scored 7
8 // Score [8]=1
// score[9], score[10]=0
Copy the code

Here, each position in the array is treated as a bucket, and the number of fractions obtained is the element of the array. This is the simplest version of bucket sorting algorithm implementation. But the real bucket sorting algorithm is much more complicated than that. This small example is just to get you started.

Algorithm principle

Bucket sort is a sorting algorithm that divides an array into a finite number of buckets. Each bucket is sorted individually (it is possible to use another sorting algorithm or continue to use bucket sort recursively).

Bucket sorting is done with the following procedure:

  1. Set a quantitative array as a series of empty buckets.
  2. Search the sequence and place the items one by one into their respective buckets.
  3. Sort each bucket that is not empty.
  4. Take the items out one by one from an empty bucket.

Buckets are used to group the numbers of an array in the order 0-9, 10-19, 20-29.

And then sort the numbers in each bucket.