What is radix sort

Radix sorting is a generalization of bucket sorting. The records to be sorted that it considers contain more than one keyword. Radix sorting is a "distributive sorting", which uses part of the information of the key value to sort the records. The elements are assigned to certain "buckets" to achieve sorting. The radix sorting method is a stable sorting method.

Radix sort

Radix sort is a generalization of bucket sort. Ranking records contain more than one keyword.

Introduction:

Radix sort (radix sort) belongs to "distribution sort" (distribution sort), also known as "bucket sort" (bucket sort) or bin sort. As the name implies, it is Through partial information of the key value, the elements to be sorted are allocated to certain "buckets" to achieve the sorting effect. The radix sorting method is a stable sorting, and its time complexity is O (nlog(r)m ), where r is the radix taken, and m is the number of heaps. At certain times, the radix sorting method is more efficient than other stability sorting methods.

Implementation method

Most Significant Digit first method, referred to as MSD method: first sort the groups by k1, record in the same group, the key code k1 is equal, and then group each group according to k2 sorting is divided into subgroups, and then the subsequent key codes continue to be sorted and grouped in this way until each subgroup is sorted according to the lowest key code kd. Then connect the groups to get an ordered sequence.

The Least Significant Digit first method, referred to as the LSD method: start sorting from kd, then sort kd-1, and repeat in sequence until k1 is sorted and an ordered sequence is obtained.

The above is the detailed content of What is radix sort. For more information, please follow other related articles on the PHP Chinese website!