Shulou(Shulou.com)05/31 Report--

This article mainly introduces the meaning of cardinality sorting in web development, it has a certain reference value, interested friends can refer to, I hope you can learn a lot after reading this article, let the editor take you to understand it.

An example of cardinality sorting

What is cardinality sorting?

Consider that although we cannot directly sort numbers in all ranges using the count array, we can consider sorting n rounds of count by the number of digits, each round sorting only one bit of the number.

In the end, you can still get the result, and you can get rid of the limit of the size of the count array, which is cardinality sorting.

Suppose the elements of our current array are: 1221, 15, 20, 3681, 277, 5420, 71, 1522, 4793.

Let's take a look at the animation and take a look at the most intuitive cardinality sorting process:

In the above example, we sort the bits first by count, then by count, followed by 100 and 1000 bits.

Finally, the final sort result is generated.

Implementation of cardinality sorting by java Code

Because cardinality sorting is actually count sorting by digits, respectively. So we can reuse the count sorting code we wrote earlier, but we just need to make some modifications.

In addition to passing in the array, the doCountingSort method also needs to pass in the sorted number of digits digit, which is represented by 1, 10, 10, 100, and 1000.

Take a look at the modified doCountingSort method:

Public void doRadixSort (int [] array, int digit) {int n = array.length;// stores the sorted array int output [] = new int [n]; / / count array, which is used to store and count the number of occurrences of each element int count [] = new int [10]; Arrays.fill (count,0); log.info ("initialize count: {}", count) / / save the number of occurrences of the data in the original array into the count array for (int item0; I 0; digit * = 10) {radixSort.doRadixSort (array,digit);}}

Take a look at the output:

Good. The results are all sorted.

Time complexity of cardinality sorting

From the calculation process, we can see that the time complexity of cardinality sorting is O (d * (nounb)), where b is the binary number of the number, for example, if we use the decimal system above, then bounded 10.

D is the number of rounds that need to be looped, that is, the maximum number of digits in the array. If the largest number in the array is represented by K, then d=logb (k).

To sum up, the time complexity of cardinality sorting is O ((nimb) * logb (k)).

When k

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.