Shulou(Shulou.com)06/03 Report--

Today, I will talk to you about the use of cardinality sorting, which may not be well understood by many people. in order to make you understand better, the editor has summarized the following contents for you. I hope you can gain something according to this article.

Cardinal sorting belongs to "distributive sorting", which assigns the elements to be sorted to some "buckets" through part of the information of key values, so as to achieve the function of sorting. Cardinal sorting is suitable for sorting data with unknown overall weights, such as time and strings.

Cardinality sorting (radix sort) belongs to "distributive sorting" (distribution sort), also known as "bucket sort" or bin sort. As the name implies, it assigns the sorted elements to some "buckets" through part of the information of key values in order to achieve the function of sorting. Cardinal sorting belongs to stable sorting, and its time complexity is O (nlog (r) m), where r is the cardinality adopted and m is the heap number. In some times, the cardinality sorting method is more efficient than other stable sorting methods.

Cardinal sorting is suitable for sorting data with unknown overall weights, such as time, strings, and so on.

Realization method

The highest bit first (Most Significant Digit first) method, referred to as MSD method: first sort and group according to K1, record in the same group, the key K1 is equal, then sort each group into subgroups according to K2, and then continue the sorting and grouping of the following keys until the subgroups are sorted according to the least bit key kd. Then connect the groups together to get an ordered sequence.

Lowest bit first (Least Significant Digit first) method, referred to as LSD method: first sort from kd, and then sort kd-1, repeat in turn, until K1 is sorted to get an ordered sequence.

After reading the above, do you have any further understanding of the use of cardinality sorting? If you want to know more knowledge or related content, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.