Radix Sort

定义 Definition

基数排序：一种非比较型排序算法，通过按数字或字符串的“位”（如个位、十位、百位；或字符位置）逐位分配与收集元素来完成排序。常见实现有 LSD（从最低位到最高位） 和 MSD（从最高位到最低位） 两种思路。主要用于整数、定长字符串等。

发音 Pronunciation

/ˈreɪdɪks sɔːrt/

例句 Examples

Radix sort can sort integers quickly when the range of digits is limited.
当数字位数有限时，基数排序可以快速排序整数。

To handle millions of IDs efficiently, the system uses an LSD radix sort with counting buckets for each digit.
为高效处理数百万个编号，系统使用从最低位开始的基数排序，并为每一位设置计数桶。

词源 Etymology

radix 源自拉丁语 radix，意为“根”。在数学与计算中常指“基数/底”（例如进制的“基”），因此 radix sort 直译可理解为“按进制的各位（基）来排序”。sort 来自古法语 sortir（分类、排列），后引申为“排序”。

相关词 Related Words

• Bucket
• Counting
• Digit
• Key
• LSD
• MSD
• Stable
• Algorithm

文学与经典著作 Notable Works

• The Art of Computer Programming, Volume 3: Sorting and Searching（Donald E. Knuth）：在排序章节中讨论了包括基数排序在内的多种方法。
• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）：在非比较排序相关内容中介绍基数排序及其与计数排序的关系。
• Algorithms（Robert Sedgewick, Kevin Wayne）：在排序算法部分讲解基数排序的思想与实现变体。