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

This article mainly explains "what is the cardinality sort of data structure and algorithm". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "what is the cardinality sort of data structure and algorithm"?

Cardinality sort

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

Cardinality sorting (radix sort) belongs to "distributive sorting" (distribution sort), also known as "bucket sort" or bin sort, which assigns the sorted elements to some buckets through the values of each bit of the key value, to achieve the function of sorting.

Cardinal sorting belongs to the sort of stability, and the method of cardinality sorting is a stable sorting method with high efficiency.

Cardinal sorting is an extension of bucket sorting.

Cardinal ordering was invented by Herman Holly in 1887. It is implemented by cutting integers into different digits and then comparing them separately by each digit.

The basic idea of sorting

Unify all the values to be compared into the same digital length, with zeros in front of the shorter digits. Then, starting from the lowest bit, sort it one by one. In this way, the sequence becomes an ordered sequence from the lowest order to the highest order.

Code case package com.xie.sort; public class RadixSort {public static void main (String [] args) {int [] arr = new int [8000000]; for (int I = 0; I

< 8000000; i++) { arr[i] = (int)(Math.random()*800000000); } long start = System.currentTimeMillis(); radixSort(arr); long end = System.currentTimeMillis(); System.out.println("耗时："+(end-start)+"ms"); /* 800万数据，耗时：939ms */ } //基数排序 public static void radixSort(int[] arr) { int max = arr[0]; for (int i = 1; i < arr.length; i++) { if (arr[i] >

Max) {max = arr [I];}} / / the maximum number of digits in the array int maxLength = (max + ") .length () / / the first round (sorting for the bits of each element) / / defines a two-dimensional array, representing 10 buckets, and each bucket is an one-dimensional array / / 1. The two-dimensional array contains 10 one-dimensional arrays / / 2. In order to prevent data overflow when putting in numbers, each one-dimensional array (bucket) is set to arr.length / / 3. Cardinality sorting is the classic algorithm int [] [] bucket = new int [10] [arr.length] that uses space for time; / / in order to record how much data is actually stored in each bucket, we define an one-dimensional array to record the number of data put in each bucket. / / bucketElementCounts [0], which records the number of data put into the bucket [0] bucket. Int [] bucketElementCounts = new int [10]; / / according to the order of the bucket (the subscript of the one-dimensional array is taken out in turn and put into the original array) int index = 0; for (int I = 0, n = 10; I < maxLength; itrees, n * = 10) {for (int j = 0; j < arr.length) Int digitOfElement = arr [j] / n% 10; / / Let bucket [digitOfElement] [bucketElementCounts [digitOfElement]] = arr [j]; bucketElementCounts [digitOfElement] + +;} OfElement = 0 / / iterate through each bucket and put the data in the bucket into the original array for (int k = 0; k < bucketElementCounts.length) If there is data in the bucket, put it into the original array if (bucketElementCounts [k]! = 0) {/ / the k-th bucket (that is, the k-th one-dimensional array) in the loop bucket. For (int l = 0; l < bucketElementCounts [k]; lump +) {/ / take the element into arr arr [index] = bucket [k] [l]; index++;}} bucketElementCounts [k] = 0 } cardinality sort description

Cardinal sorting is to exchange space for time. When sorting massive data, it is easy to cause OutOfMemoryError.

The cardinality is stable in sorting. [note: assuming that there are multiple records with the same keywords in the sequence of records to be sorted, the relative order of these records remains unchanged, that is, r [I] = r [j] in the original sequence, and r [I] is before r [j], while in the sorted sequence, r [I] is still before r [j], the algorithm is said to be stable, otherwise unstable.

Cardinality sort of arrays with negative numbers

At this point, I believe you have a deeper understanding of "what is the cardinality sorting of data structure and algorithm". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.