基数ソートとは何ですか

基数ソートはバケット ソートを一般化したものです。基数ソートは、ソート対象のレコードに複数のキーワードが含まれているとみなします。基数ソートは、キー値の情報の一部を使用してソートする「分散ソート」です。レコード。要素はソートを実現するために特定の「バケット」に割り当てられます。基数ソート方法は安定したソート方法です。

#基数ソート

基数ソートはバケット ソートを一般化したものです。ランキング レコードには複数のレコードが含まれます。キーワード。

はじめに:

基数ソート (基数ソート) は、「分散ソート」 (分散ソート) に属し、「バケット ソート」 (バケット ソート) またはビン ソートとも呼ばれます。キー値の部分情報を通じて、ソート対象の要素が特定の「バケット」に割り当てられ、ソート効果が得られます。基数ソート方法は安定したソートであり、その時間計算量は O (nlog(r)m) ), ここで、r は取得される基数、m はヒープの数です。特定の時点では、基数ソート方法が他の安定性ソート方法よりも効率的です。

実装方法

MSD 法と呼ばれる最上位桁優先法: まずグループを k1 で並べ替え、同じグループに記録し、キー コード k1 が等しい後、それぞれをグループ化します。 k2 ソートによるグループはサブグループに分割され、各サブグループが最低のキー コード kd に従ってソートされるまで、後続のキー コードがこの方法でソートおよびグループ化され続けます。次に、グループを接続して順序付けされたシーケンスを取得します。

LSD 法と呼ばれる最下位桁優先法: kd からソートを開始し、次に kd-1 をソートし、k1 がソートされて順序付けされたシーケンスが得られるまで順番に繰り返します。

以上が基数ソートとは何ですかの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。