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

This article mainly shows you the "Java sorting algorithm count sorting how to achieve", the content is easy to understand, clear, hope to help you solve your doubts, the following let Xiaobian lead you to study and learn "Java sorting algorithm count sorting how to achieve" this article.

Counting sorting is a non-comparative sorting algorithm, which uses an auxiliary array to count the numbers that appear in the array, to convert elements to subscript, and to convert subscript to elements.

Advantages and disadvantages of counting sorting

Advantages: fast

Disadvantages: the range of data is very large and sparse, which will lead to large auxiliary space and waste of space.

Scope of use: suitable for dense data or small scope.

Train of thought

1. Find the largest element max

two。 Initialize an array of max+1

3. Store the count of each element at its own index in the array

4. Cumulative sum of elements in a storage count array

5. The index of each element of the original array found in the array

The counting and sorting code implements public class CountingSort {private static int [] countingSort (int [] arr) {/ / 1, calculates the maximum and minimum values, and calculates the length of the intermediate array: the intermediate array is used to record the frequency of each value in the original data int min = arr [0], max = arr [0] For (int I: arr) {if (I > max) {max = I;} if (I

< min) { min = i; } } //2、有了最大值和最小值能够确定中间数组的长度 //例如存储 5-0+1=6 int[] countArray = new int[max - min + 1]; //3、循环遍历旧数组计数排序: 就是统计原始数组值出现的频率到中间数组B中 for (int i : arr) { countArray[i - min] += 1; //数的位置上+1 } //4、统计数组做变形，后边的元素等于前面的元素之和 for (int i = 1; i < countArray.length; i++) { countArray[i] += countArray[i - 1]; } //5、倒序遍历原始数组，从统计数组中找到正确的位置，输出到结果数组 int[] resultArray = new int[arr.length]; for (int i = arr.length - 1; i >

= 0; iMurray -) {/ / assign the resultArray to the current position of the resultArray [countArray [arr [I]-min]-1] = arr [I]; / the value to the location of the countArray-countArray [arr [I]-min] -;} return resultArray } public static void main (String [] args) {int [] arr = {1 sortedArr 28) 3 21, 11 7, 6 18}; int [] sortedArr = countingSort (arr); System.out.println (Arrays.toString (sortedArr));}}

Time complexity: O (nymk)

The above is all the contents of the article "how to achieve the count sorting of Java sorting algorithm". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

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.