ホームページ  >  記事  >  基数ソートは何に役立ちますか?

基数ソートは何に役立ちますか?

藏色散人
藏色散人オリジナル
2020-07-02 09:37:002908ブラウズ

基数ソートは「分散ソート」です。キー値情報の一部を通じて、ソート対象の要素を特定の「バケット」に割り当て、ソート効果を実現します。基数ソートは、時間などのデータのソートに適しています総重量が不明な文字列。

基数ソートは何に役立ちますか?

基数ソートは「分散ソート」であり、「バケット ソート」またはビン ソートとも呼ばれます。名前が示すように、ソートする要素を割り当てます。基数ソート方法は安定したソートであり、その時間計算量は O (nlog (r)m) です (r は基数、m は m です)。はヒープの数です。特定の時点では、基数ソート方法が他の安定性ソート方法よりも効率的です。

基数ソートは、時間や文字列など、全体の重みが不明なデータのソートに適しています。

実装方法

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

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

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

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。