ソート(3)カウントソートとベースソート

前回は時間複雑度がO(nlogn)に近いアルゴリズムを書き終えたが,今回はまず時間複雑度O(n)の2つのアルゴリズムを書き終えた.これらはそれぞれカウントソートと基数ソートであり,O(nlogn)はすでに比較に基づくソートアルゴリズムの下限であるため,この2つのアルゴリズムは比較を必要としない.
一、カウントソート
時間複雑度O(n),空間複雑度O(k),kは入力シーケンスの値の範囲(最大値−最小値)であり,安定である.カウント・ソートは、一般に、会社員の身長体重情報のソートなど、既知の入力値の範囲が比較的小さい場合に使用されます.
アルゴリズムの導論の中のカウントソートは大体このような考え方である:n個の入力要素のそれぞれが0からkの間の整数であると仮定し、各入力要素xに対して、x未満の要素の個数を確定し、この情報があれば、xを最終出力配列の位置に直接置くことができ、例えば、17個の要素がx未満であれば、xは18番目の出力位置に属する.いくつかの要素が同じである場合、シナリオは少し変更します.
この方法はよく理解できないし、コードを書くのも面倒だと思います.だから私の次のコードはバケツのソートの思想で実現しました.
この実装は,ハッシュ内のキー値変換思想に似ており,入力した値をバケツのシーケンス番号(バケツ配列の下付き)にマッピングし,バケツ配列を繰り返して要素を逆にする.プロセスは、入力シーケンスの値の範囲kに基づいて、k個のバケツ(大きさkの配列で表され、下付きはバケツのシーケンス番号で表され、値はバケツ内の要素の個数で表される)を作成する.入力配列を繰り返し、該当する位置のバケツに入れ、バケツを順番に出してください.
例えば、入力配列Aが{3,5,1,2,4,3}であり、値の範囲が1~5であると仮定して、バケツ5個、シーケンス番号1,2,3,4,5を作成する.バケツを詰める時に入力配列を繰り返し、A[0]=3、それを3番バケツに置く.A[1]=5、5番バケツに入れる.1を1番バケツに・・・最後の3を3番バケツに.現在、3番のバケツの値は2で、他のバケツの値は1で、バケツの配列をもう一度巡って、バケツを順番に倒して、要素が倒される順番がソートの順番です.

import java.util.*;
 
public class CountingSort {
    public int[] countingSort(int[] A, int n) {
        //            ，      
        int max=A[0];
        int min=A[0];
        for(int i=0;imax)
                max=A[i];
            if(A[i]0;k--){
                A[i++]=j+min;
            }
        }
        return A;
    }
}

二、基数ソート
1.マルチキーワードソートの考え方
基数ソート時に、マルチキーワードソートの考え方を用いて単一論理キーワードをソートする方法.キーワードの前後順に基数ソートは高位優先法と低位優先法に分けられる.
例えば、トランプのソートでは、色(黒桃>梅>赤桃>角片と仮定)の優先度が顔値より高く、色が主キーであり、顔値が次キーであることを規定します.私たちはまず花色によってトランプを秩序ある4つの山に分けて、それからそれぞれの山に対して顔値によってソートすることができます.これがいわゆる高位優先法です.統合が少し似ているような気がしますか?これは,ここでも分治法思想を利用したソートであるからである.低位優先法則は上とは逆である.まず、トランプを額面で13山に分けて(分配操作と呼ばれます)、この13山を順番に小さくから大きく重ねて(収集)、それから花色に対して分配収集操作を実行して、それからトランプは秩序があります.
また値を見ると数字の例です.{23412,73252,31}と入力すると、ビット、10ビット、100ビットの数字を4つのキーワードと見なし、優先度が順次上昇します.以上の考えによれば、まず百位で{73,31;112;234252}(0;1;2)の3つの山に分け、それぞれの山の中で10位を押して、{31,73;112;234252}を押して、さらに1位を押します.これが高位優先であり、低位優先も上記と同じ理屈である.
一般的に低位優先法は高位より簡単である.高位優先は分治法思想であるため,サブセットを同じ方法で並べ替えることは再帰的な過程である.下位優先法は、x回の割り当て収集操作でソートを完了することができ、xはキーワードの数に依存する.
2.バケツソート思想基数ソートを実現
本で述べた基数ソートアルゴリズムは,バケツの考え方を用いて低位優先法を実現し,入力数値の各ビットをキーワードとしてソートする.時間複雑度O(xn)=O(n)は,収集操作を割り当てるたびに線形時間であるため,キーワード個数xも定数である.空間複雑度も大きく減少し,O(1)であり,バケツの個数も定数であった.安定したソートアルゴリズムです.しかし,基数ソートが非常に柔軟ではないため,入力データ型がやや変化し,書き換え,キーワードの再規定などの問題が発生する可能性がある.したがって,基数ソートは他のアルゴリズムで広く使用されていない.
アルゴリズムの実装について説明します.バケツを利用して思想を並べ替えるのも.入力データはすべて10進数で、いずれも4桁以内の数であると仮定します.バケツ10個、番号0、1、2、3、4、5、6、7、8、9を用意します.まず,ビット上の数値に基づいてどのバケツに入るかを選択し,次いで順番に逆さにして最初のソートを行った.そして10位の数でバケツに入ってから出します.そして100ビット,千ビット,4回の割当て収集を行う.
カウントソートアルゴリズムのバケツは要素の個数を格納するだけなので、int値1つでいいです.しかし、バケツには要素の数値が格納されているので、バケツごとに別の方法で表示されます.私が次のコードに書いたのはint [][] B = new int [10][n];で、10個のバケツを作成しました.各バケツはnの大きさの配列です.各バケツには最大n個の要素が入る可能性があるからです.しかし、このように書くスペースはコストがかかり、多くのスペースが浪費されています.もっと良い方法はチェーンテーブルでバケツの中の要素を格納するべきです(しかし、私は書き終わってから気づいたので、直すのがおっくうです...).バケツは1つのキューで表されるはずです.実はオンラインで問題を作るなら、完全にQueueクラスで表すことができて、簡単です.私は前にオンラインの問題をする時1回スタックを使う必要があって、それから私自身はスタックを書いて、時間をかけて言わないで、また間違いました...しかし、実は完全に優先キュークラスで補助することができます.面接では面接官があなたの勉強を考察したいかもしれませんが、オンライン問題はOCだけでいいですか.結局javaを使っています.自分がまだjavaに対して熟知していないことを反省して、アルゴリズムの問題をするのはやはりc/c++の思惟の中にとどまって、javaの特性を利用していません.下のコードは、書くときに考えがはっきりしていないし、チェーンテーブルでバケツをリストしていないので、少し散らかっているかもしれませんが、みんなで見てください.

package fuckingtest;
import java.util.*;
public class RadixSort {
    public int[] radixSort(int[] A, int n) {
        //     B    ,                 
        int[][] B= new int[10][n+1];
        for(int i=0;i<10;i++)
            for(int j=0;j0&&k<=B[j][0];k++){
                    A[i++]=B[j][k];
                }
                B[j][0]=0;
            }
        }
        return A;       
    }
    int getNum(int x,int d){
        int[] a={1,1,10,100,1000};
        System.out.println((x/a[d])%10);
        return (x/a[d])%10;
    }    
    public static void main(String[] args) {
        int[] r=new int[6];
        int[] a=new int[]{109,551,32,4,294,6};
        RadixSort h = new RadixSort();
        r = h.radixSort(a,6);
        for(int t:r){
            System.out.println(t);
        }
    }
}