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

This article mainly introduces "what are the advantages of counting sorting". In daily operation, I believe many people have doubts about the advantages of counting sorting. The editor consulted all kinds of data and sorted out simple and easy-to-use operation methods. I hope it will be helpful to answer the doubts about "what are the advantages of counting sorting"! Next, please follow the editor to study!

Counting and sorting

Counting sorting is a non-comparison-based sorting algorithm, which was proposed by Harold H. Seward in 1954. Its advantage is that when sorting integers in a certain range, its complexity is equal (n = k) (where k is the range of integers), which is faster than any comparative sorting algorithm. [1] of course, this is a way to sacrifice space for time, and when O (k) > O (nlog (n)), it is not as efficient as comparison-based sorting (the theoretical lower limit of time complexity of comparison-based sorting is O (nlog (n)), such as merge sorting, heap sorting).

Algorithm thought

The counting sort has additional restrictions on the input data: 1, the elements of the input linear table belong to the finite poset S; 2, let the length of the input linear table be n, | S | = k (indicating the total number of elements in the set S is k), then krypo (n). Under these two conditions, the complexity of counting sorting is O (n). The basic idea of counting sorting is to determine the number of elements whose value is less than x for each element x in a given input sequence (instead of comparing the size of each element here, it is determined by counting and accumulating element values). Once you have this information, you can store x directly in the correct location of the final output sequence. For example, if only 17 elements in the input sequence have values less than the value of x, x can be stored directly in the 18th position of the output sequence. Of course, if there are multiple elements with the same value, we can't put them in the same place in the output sequence, so the above scheme needs to be modified appropriately.

Algorithm thought

Counting sorting is a stable sorting algorithm, which can sort the array containing n elements in linear time (O (n ~ k)), where the array elements are greater than or equal to 0 and less than or equal to k.

When sorting the elements A [x] of the input array A, we first record the number of elements of A [x] in the counting array C, and then calculate the position in the output array B according to the values in C. Considering the existence of multiple equal elements, the data in B is maintained and one needs to be subtracted from B if the same data exists in A.

The code implements public static int [] countSort (int [] arr) {int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; int [] res = new int [arr.length]; / O (n) for (int j: arr) {min = Math.min (j, min); max = Math.max (j, max) } int [] pos = new int [max + 1]; / O (k) for (int I = 0; I < arr.length; iTunes +) {/ / because the count here starts at 1. Pos[ arr [I]] +;} for (int I = 1; I < pos.length; I +) {pos [I] = pos [I] + pos [I-1];} for (int I = 0; I < arr.length) Res +) {/ / the count starts at 1, and we rearrange the return res; [] should start at 0 [posarr [I]-1] = arr [I]; pos[ arr [I]] -;} arr} summary

The essence of counting sorting is to store a mapping relationship in an array to save its location, and then traverse the original array to sort it from the position array.

The sorted array must be a non-negative integer because the subscript of the array is limited.

The time complexity of counting and sorting is O (nsequk), n is the length to be sorted, and k is the maximum value of the element in the array.

At this point, the study of "what are the advantages of counting sorting" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.