Cardinality sorting - common sorting method (2/8)

Catalog

1、 What is cardinal sort

2、 The process of sorting cardinality

1、 step

2、 Picture demonstration

3、 Code implementation

---

1、 What is cardinal sort

Cardinal sort is a non comparative sort , The common comparison sort is bubbling , Directly inserted into the , Wait . These sorts require comparison and exchange to sort the data . Instead of the comparison sort, there is usually a cardinal sort , Count sorting , Bucket sorting, etc . These sorts do not need to be compared . The specific steps are as follows ：

2、 The process of sorting cardinality

1、 step

We need to establish 10 A queue （ Arrays can also ）, Respectively from the 0 Number to 9. Then the data to be sorted According to the position The numbers of are stored in the queue respectively . After all are queued , From number 0 The queue of starts to get out of the queue . After the same reason According to ten , Hundred bit , Thousands are queued , And out of the line . Until it reaches the highest point in this set of data .

2、 Picture demonstration

We give a set of data as follows ： The data is out of order .

1、 Enter the queue by single digit word  

2、 Data after leaving the queue  

3、 Enter the queue by ten digits   

4、 Outgoing queue  

5、 Enter the queue by hundreds  

6、 Outgoing queue  

7、 In thousands （ highest ）  Numbers are queued  

8、 Outgoing queue , That is, orderly data  

3、 Code implementation

import java.util.concurrent.ArrayBlockingQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:  Dongguan hehe 
 * Date:2022-06-23
 * Time:15:24
 */
public class RadixSort {
    public static void radixSort(int[] array) {
        // Create ten buckets （ queue ）
        List<Queue<Integer>> queueList = new ArrayList<>(10);
        for (int i = 0; i < 10; i++) {
            queueList.add(new ArrayBlockingQueue<Integer>(1000));
        }
        // Find the maximum value in the array 
        int max = array[0];
        for (int k : array) {
            if (max < k) {
                max = k;
            }
        }
        // Record the maximum number of digits 
        int count = 0;
        while (max != 0) {
            count++;
            max /= 10;
        }
        // Start sorting 
        //x Represents the current base digit 
        int x = 0;
        while (x < count) {
            for (int i = 0; i < array.length; i++) {
                int num = getFigure(array[i], x);
                queueList.get(num).offer(array[i]);
            }
            int j = 0;
            for (int i = 0; i < array.length; i++) {

                if (j <= 9 && queueList.get(j).isEmpty()) {
                    j++;
                    // Because the current queue is empty , You need to skip this cycle i++, But at this time i Situated array[i] No assignment , So we need to i--
                    i--;
                    continue;
                }
                array[i] = queueList.get(j).poll();
            }
            x++;
        }
    }

    /**
     *  Back to page k What is the value of the bit （k=0,1,2）（ individual , Ten , hundred ）
     * @param i
     * @param k
     * @return
     */
    public static int getFigure(int i, int k) {
        int arr[] = {1, 10, 100, 1000, 10000, 100000, 1000000};
        return (i / arr[k]) % 10;
    }

    public static void main(String[] args) {
        int[] arr = {65, 43, 5, 7, 4, 5, 76, 23, 4, 765, 42, 6, 7, 8};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

If we have a large amount of data to be queued, we can increase the size of the created queue , If the data to be scheduled is large, it can be changed getFigure Data in .

Of course, you can also use arrays to implement , If you use an array to implement it, you should pay attention to the first in first out array .