Radix sort

• Radix sort is to sort the last first, and then to inverse the second rank, and then the third from bottom, until the last, every time of every sort, will increasingly orderly

• Since each number has bits 0-9, we need 10 buckets to sort

• How do we figure out what we get in the/ten/hundreds place? int radix = (int) (a[j] / Math.pow(10, i)) % 10; Since the ones place is the remainder of the whole number, divided by 10 if it is the tens place and then mod, divided by 100 if it is the hundreds place, we can use Math’s POw function to determine how much we divide each time

• Time complexity bit O(KN), space complexity O(N + K), stable sorting, and non-in-situ sorting

  

• Code implementation

  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.LinkedList;
  
  / * * *@Description: Radix sort *@Author: LinZeLiang
   * @Date: the 2020-10-11 * /
  public class RadixSort {
  
      public static void main(String[] args) {
          int[] a = {9.54.3.6.43.11.27.98.43.5.2.89.1.4.8.16.20};
  
          radixSort(a);
  
          System.out.println(Arrays.toString(a));
  
      }
  
      private static void radixSort(int[] a) {
          // Get the maximum value
          int max =a[0];
          for (int i = 1; i < a.length; i++) {
              if(max < a[i]) { max = a[i]; }}// Get the largest number of digits
          int num = 0;
          while(max ! =0) {
              max /= 10;
              num++;
          }
  
          // Create 10 buckets
          int bucketNum = 10;
          ArrayList<LinkedList<Integer>> bucketList = new ArrayList<>(bucketNum);
  
          // Initialize the bucket
          for (int i = 0; i < bucketNum; i++) {
              bucketList.add(new LinkedList<Integer>());
          }
  
          // Sort buckets on each trip
          for (int i = 0; i < num; i++) {
              for (int j = 0; j < a.length; j++) {
                  // Get the last digit
                  // For the second loop, divide by 10 and then mod. This way, we can get fixed bits in real time without changing the original array
                  int radix = (int) (a[j] / Math.pow(10, i)) % 10;
                  // Put it in the appropriate bucket
                  bucketList.get(radix).add(a[j]);
              }
  
              // Merge the original array
              int k = 0;
              for (LinkedList<Integer> integers : bucketList) {
                  for (Integer integer : integers) {
                      a[k++] = integer;
                  }
                  // Empty the bucket for the next cycleintegers.clear(); }}}}Copy the code

Top 10 Ranking Summary

Let’s take a look at ten of their algorithmic properties: