基数ソートのヒント 1 つ、ソート方法 2 つ、ソートアルゴリズム 3 つ

[[421174]]

基数ソート

コンセプト

基数ソートは、整数をビットごとにソートする非比較整数ソート アルゴリズムです。基数ソートは、カウントソートの制限を打ち破り、広範囲のデータをソートするのに適します。整数は文字列 (名前や日付など) や浮動小数点数を特定の形式で表現することもできるため、基数ソートは整数に限定されません。

2つのソート方法

最下位ビット優先 (LSD): ビットを最下位ビットから最上位ビットの順に並べ替えます。

最上位ビット優先 (MSD): データ ビットを最上位ビットから最下位ビットの順に並べ替えます。

ビット分割のヒント

arr[i] / digit % 10、ここでdigitは10^nです。

LSDソートアルゴリズムの実装

アルゴリズムのアイデア

ビットによるカウントソート

アルゴリズム実装コード

/**
     * ビットごとにカウントして並べ替える
     * @param arr
     * @param 除算
     * @戻る 
     */
プライベートスタティック  int [] countingSort( int [] arr, int除算) { 
 
 int [] バケット = 新しいint [10];
 ( int i = 0; i < arr.length; i++) {
        バケット[arr[i] / 除算 % 10]++;
    } 
 
 ( int i = 1; i < バケットの長さ; i++) {
        バケット[i] = バケット[i-1] + バケット[i];
    } 
 
 int [] sortArr = 新しいint [arr.length];
 ( int i = arr.length - 1; i >= 0; i --) {  
 int位置 = バケット[arr[i] / 除算 % 10];
        sortArr[位置 - 1] = arr[i];
        バケット[arr[i] / 除算 % 10] --;  
    }
 sortArrを返します。
 } 
 
公共 静的  int [] radixSort( int [] arr) {
    // 配列内の最大値を見つける
整数 最大値= arr[0];
 ( int i = 0; i < arr.length; i++) {
最大値= Math.max (arr[i]、最大値) ;
    }
    // ビット順に並べ替え
整数数字 = 1;
 ( int i = 1; i < max ; digit*=10, i = digit) {
        arr = countingSort(arr, 数字);
    }
 arrを返します。
 }

ソート検証:

公共 静的void main(String[] args) {
 int [] arr = {999,1000,1001,1000,999,1005};
     System.out.println ( "ソート前:" + JSON.toJSONString(arr));
 int [] sortArr = radixSort(arr);
     System.out.println ( "ソート後:" + JSON.toJSONString(sortArr));
 }

ソート前: [999, 1000, 1001, 1000, 999, 1005] ソート後: [999, 999, 1000, 1000, 1001, 1005]

MSDソートアルゴリズムの実装

アルゴリズムのアイデア

最上位ビットから始めて、ビットごとにグループ化します。グループ内の要素数が 1 より大きい場合は、最後のビットに達するまで次のビットを再帰的にグループ化し、要素数 = 1 を収集します。

アルゴリズムの手順

• 最大値を照会し、最高位の桁の基数を取得します。 Math.pow(10, 数字 - 1)
• ビットごとにグループ化し、バケットに保存します。 groupBucket[位置][groupCounter[位置]] =arr[i];
• グループ内の要素数が 1 より大きい場合、次のグループ化は再帰的に実行されます。 if (groupBucket[i] > 1) {int[] tmp = msdSort(copyArr, radix / 10);}
• グループ内の要素数 = 1、要素を収集します。 sortArr[インデックス++] = groupBucket[i][0];

たとえば、配列 [333, 1002, 1001, 1000, 333, 1003, 2000] をソートするには、次の手順に従います。

アルゴリズム実装コード

公共 静的  int [] ソート( int [] arr){ 
 
整数 最大値= arr[0];
 ( int i = 0; i < arr.length; i++) {
        // 最大値を取得する
最大値= Math.max (arr[i]、最大値) ;
    } 
 
    // 最大値を取得する
int digit = getDataDigit(最大);
    // 最大値のカーディナリティを計算する
int radix = new Double (Math.pow(10, digit - 1)).intValue();
    //msd 基数ソート
msdSort(arr, radix)を返します。
 } 
 
 /**
     * MSD基数ソート
     * @param arr
     * @param 基数
     * @戻る 
     */
公共 静的  int [] msdSort( int [] arr, int基数) { 
 
    // 単位の桁まで再帰的にグループ化して終了
    基数 <= 0 の場合
arrを返します。
    } 
 
    // グループカウンター
int [] groupCounter = 新しいint [10];
    // グループバケット
int [][] groupBucket = 新しいint [10][arr.length];
    // ソートする配列を走査し、ビットごとにグループ化します
( int i = 0; i < arr.length; i++) {
        // グループ化バケットの位置を計算する
int位置 = arr[i] / 基数 % 10;
        // 要素をグループに保存する
        groupBucket[位置][groupCounter[位置]] = arr[i];
        // 現在のグループ数に 1 を加算
        groupCounter[位置]++;
    } 
 
整数 インデックス= 0;
 int [] sortArr = 新しいint [arr.length]; 
 
    // グループカウンタを走査する
( int i = 0; i < groupCounter.length; i++) {
        // グループ内の要素数 > 1、再帰グループ化
        グループカウンタ[i] > 1の場合{
 int [] copyArr = Arrays.copyOf(groupBucket[i], groupCounter[i]);
            // 再帰的なグループ化
int [] tmp = msdSort(copyArr, 基数 / 10);
            // 再帰的にグループ化された要素を収集する
( int j = 0; j < tmp.length; j++)の場合{
                sortArr[インデックス++] = tmp[j];
            }
        }そうでない場合 (groupCounter[i] == 1) {
            // グループ内の要素数が 1 である要素を収集します
            sortArr[インデックス++] = groupBucket[i][0];
        }
    } 
 
 sortArrを返します。
 } 
 
 /**
     * データのビット数を取得する
     * @param データ
     * @戻る 
     */
公共 静的  int getDataDigit( intデータ) {
    //整数 インデックス= 0;
    // int数字 = 1;
    // while (データ / 数字 > 0) {
    // 数字 *= 10;
    //インデックス++;
    // }
    //戻る 索引; 
 
 String.valueOf(data).length()を返します。
 }

並べ替え結果を確認します。

公共 静的void main(String[] args) {
 int [] arr = {333,1002,1001,1000,333,1003,2000};
    System.out.println ( "ソート前:" + JSON.toJSONString(arr));
 int [] sortArr = sort(arr);
    System.out.println ( "ソート後:" + JSON.toJSONString(sortArr));
 }

ソート前: [333, 1002, 1001, 1000, 333, 1003, 2000] ソート後: [333, 333, 1000, 1001, 1002, 1003, 2000]

3 方向セグメンテーション文字クイックソート

アルゴリズムのアイデア

文字列をビットごとに 3 つの間隔に分割します。v 未満の間隔: [lo, lt-1]、v に等しい間隔: [lt, gt]、v より大きい間隔: [gt+1, hi] とし、3 つの間隔を順番に再帰的に分割します。

アルゴリズムの手順

• v 未満の値に対してウォッチドッグ タイマー lt を定義し、v より大きい値に対してウォッチドッグ タイマー gt を定義します。
• 3 つの間隔をビット単位の比較で分割します。
• 3 つの間隔にわたって再帰します。

アルゴリズム実装コード

/**
     * 文字列をビットごとに3つの区間に分割する
     * 1. v未満の区間: [lo, lt]
     * 2. v区間に等しい: [lt,gt]
     * 3. v より大きい間隔: [gt+1,hi]
     * @param arr
     * @param lo
     * @param こんにちは
     * @param d
     */
公共 静的void sortStr(String[] arr, int lo, int hi, int d){
    （高<=低）の場合{
戻る;
    }
    // v 未満の値にはゲートキーパー lt を、v より大きい値には gt を定義します。
 int lt = lo、gt = hi、i = lo + 1、v = charAt(arr[lo]、d);
    (i <= gt){
 int t = charAt(arr[i], d);
        （t<v）の場合{
            交換(arr、i++、lt++);
        }そうでなければ (t > v) {
            交換(arr, i, gt --);  
        }それ以外{
            私は++;
        }
    } 
 
    // 再帰間隔が v 未満
    sortStr(arr, lo, lt - 1, d);
    // v の区間を再帰的に等しくする
    (v >= 0) の場合 {
        sortStr(arr, lt, gt, d + 1);
    }
    // 再帰が v より大きい
    sortStr(arr, gt + 1, hi, d);
 }
プライベートスタティック  int charAt(文字列 s, int d) {
    d < s.length() の場合 {
 s.charAt(d)を返します。
    }
 -1 を返します。
 }
公共 静的void exch(String[] arr、 int sourceIdx、 int targetIdx) {
    文字列 tmp = arr[sourceIdx];
    arr[ソースID] = arr[ターゲットID];
    arr[ターゲットID] = tmp;
 }
検証結果: 
 
公共 静的void main(String[] args) {
     String[] a = new String[]{ "by" 、 "air" 、 "she" 、 "shell" 、 "the" 、 "okay" 、 "bump" 、 "shirt" 、 "shells" 、 "sh" 、 "the" 、 "shells" 、 "the" };
     System.out.println ( "ソート前:" +JSON.toJSONString(a));
     sortStr(a, 0, a.length - 1, 0);
     System.out.println ( "ソート後:" +JSON.toJSONString(a));
 }

並べ替え前: ["by","air","she","shell","the","okay","bump","shirt","shells","sh","the","shells","the"] 並べ替え後: ["air","bump","by","okay","sh","she","shell","shells","shells","shirt","the","the","the"]

3つのソートアルゴリズムの比較

要約する

基数ソートは安定した非比較ソートであり、大きなデータ範囲に適しています。