Java基数並べ替えradix sort原理と用法解析

基数並べ替え（バケツ並べ替え）の説明
基数並べ替え（radix sort）は「分配式並べ替え」（distribution sort）に属し、また「桶子法」（bucket sort）またはbin sortとも呼ばれています。名前の通り、キーの各桁の値を通して、並べ替えたい元素をいくつかの「桶」に割り当てて、並べ替えの役割を果たします。
基数秩序化法は安定性のある秩序化であり，基数秩序化法は効率の高い安定性秩序化法である。
基数並べ替え(Radix Sort)はバケツ並べ替えの拡張です。
基数ランキングは1887年にヘルマン・ホレが発明した。これはこのように実現されています。整数を桁数ごとに異なる数字にカットして、それぞれの桁数で比較します。
基数並べ替えの基本思想
すべての比較すべき数値を同じ数桁の長さに統一して、数桁の短い数の前でゼロを補います。そして、最下位から順に並べ替えます。このように、最下位の順序から最上位の順序付けが完了するまで、数列は秩序化されたシーケンスになる。
特徴
空間が時間を変えて、安定しています。
コード

package cn.guizimo.sort;

import java.util.Arrays;

public class RadixSort {
  public static void main(String[] args) {
    int arr[] = {53,45,6,378,15,234,78};
    System.out.println("   ");
    System.out.println(Arrays.toString(arr));
    radixSort(arr);
    System.out.println("   ");
    System.out.println(Arrays.toString(arr));
  }

  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];
      }
    }
    //    
    int maxLength = (max + "").length();

    int[][] bucket = new int[10][arr.length];
    int[] bucketElemtCounts = new int[10];

    for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
      for (int j = 0; j < arr.length; j++) {
        int digitOfElemt = arr[j] / n % 10;
        bucket[digitOfElemt][bucketElemtCounts[digitOfElemt]] = arr[j];
        bucketElemtCounts[digitOfElemt]++;
      }
      int index = 0;
      for (int k = 0; k < bucketElemtCounts.length; k++) {
        if (bucketElemtCounts[k] != 0) {
          for (int l = 0; l < bucketElemtCounts[k]; l++) {
            arr[index++] = bucket[k][l];
          }
        }
        bucketElemtCounts[k] = 0;
      }
      System.out.println(" "+(i+1)+"   ");
      System.out.println(Arrays.toString(arr));
    }

  }
}

テスト

テスト速度

package cn.guizimo.sort;

import java.util.Arrays;

public class RadixSort {
  public static void main(String[] args) {
    int max = 80000;
    int[] arr = new int[max];
    for (int i = 0; i < max; i++) {
      arr[i] = (int)(Math.random() * 80000);
    }
    long date1 = System.currentTimeMillis();
    radixSort(arr);
    long date2 = System.currentTimeMillis();
    System.out.println("       "+max+"      ："+(date2-date1));
  }

  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];
      }
    }
    //    
    int maxLength = (max + "").length();

    int[][] bucket = new int[10][arr.length];
    int[] bucketElemtCounts = new int[10];

    for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
      for (int j = 0; j < arr.length; j++) {
        int digitOfElemt = arr[j] / n % 10;
        bucket[digitOfElemt][bucketElemtCounts[digitOfElemt]] = arr[j];
        bucketElemtCounts[digitOfElemt]++;
      }
      int index = 0;
      for (int k = 0; k < bucketElemtCounts.length; k++) {
        if (bucketElemtCounts[k] != 0) {
          for (int l = 0; l < bucketElemtCounts[k]; l++) {
            arr[index++] = bucket[k][l];
          }
        }
        bucketElemtCounts[k] = 0;
      }
    }
  }
}

以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。