概要
概要
各桁を下位から順に安定ソートしていく方法です。桁数が短い整数列などで有効です。
ソート / Radix Sort（基数ソート）
各桁を下位から順に安定ソートしていく方法です。桁数が短い整数列などで有効です。
目次
このページでわかること
概要
各桁を下位から順に安定ソートしていく方法です。桁数が短い整数列などで有効です。
考え方
for each digit from LSD to MSD
stable sort by that digit要点
O(d(n + k))
O(d(n + k))
O(d(n + k))
はい / 内部のソートが安定なら
補足
前の桁で作った順序を崩さないため、内部で安定ソートが必要です。
固定長のキーに向きます。
各桁の並べ替えに Counting Sort を使うのが典型です。
動きで確認
ここでは「1 の位だけを見る」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。