Radix Sort

Idea

Radix Sort is a non-comparison integer sort: split numbers by digit, stably sort by each digit (often counting/bucket sort) from least significant to most significant to get an ordered list.

基数排序演示

17045759080224266

当前处理位：个位

下一步

Algorithm

1. Find max digit length $d$.
2. From LSD to MSD, stably sort by each digit (e.g., counting sort).
3. After $d$ passes, the array is sorted.

Pseudo-code:

function radixSort(A, d):
    for i = 1 to d:
        stably sort A by digit i (e.g., counting sort)

Complexity

• Best/worst/avg: $O(d(n+r))$, with $d$ digits and radix $r$
• Space: $O(n+r)$
• Stability: stable

Exercises

Exercise 1

Run radix sort on $A = [170, 45, 75, 90, 802, 24, 2, 66]$; show results after each digit.

参考答案

思路：按个位、十位、百位。

步骤：

1. 个位：[170, 90, 802, 2, 24, 45, 75, 66]
2. 十位：[802, 2, 24, 45, 66, 170, 75, 90]
3. 百位：[2, 24, 45, 66, 75, 90, 170, 802]

答案：如上，最终有序。

Exercise 2

What are radix sort’s time and space complexities?

参考答案

思路：复杂度与空间。

步骤：

1. 时间复杂度 $O(d(n+r))$
2. 空间复杂度 $O(n+r)$

答案：时间 $O(d(n+r))$，空间 $O(n+r)$。

PreviousMerge SortMerge sort fundamentals, algorithm flow, complexity, and practice. NextExternal SortingExternal sorting basics, common methods, complexity, and practice.