Radix Sort¶

Radix Sort is a non-comparison-based integer sorting algorithm. Its core idea is to sort the digits of numbers one by one (from the least significant digit to the most significant digit, such as units, tens, hundreds, etc.). Unlike comparison-based sorting algorithms (e.g., Quick Sort, Merge Sort), Radix Sort achieves sorting through “bucket distribution” and “collection”, making it particularly suitable for integer sorting problems.

Basic Idea of Radix Sort¶

To use Radix Sort, we first need to determine the number of digits in the largest number of the array to be sorted. For example, if the largest number in the array is 802 (which has 3 digits: units, tens, hundreds), we need to sort these 3 digits. The specific steps are as follows:

1. Determine the Number of Digits: Find the largest number in the array and calculate its number of digits (e.g., 802 has 3 digits).
2. Sort by Digits: Start from the least significant digit (units place, position 0) and proceed to the most significant digit (hundreds place, position 2). For each digit, distribute the elements of the array into different “buckets” based on the current digit, then collect the elements from these buckets in order to complete the sorting for that digit.
3. Repeat Processing: Repeat the above bucket distribution and collection operations for each digit until all digits are processed, and the array is sorted.

Python Implementation Steps¶

Here we implement Radix Sort in Python. The key steps are as follows:

def radix_sort(arr):
    # Handle empty array case
    if not arr:
        return arr

    # Find the maximum number in the array to determine the number of digits to sort
    max_num = max(arr)
    digits = len(str(max_num))  # Number of digits of the maximum number, e.g., 802 has 3 digits

    # Iterate through each digit (from least significant to most significant, starting at digit 0)
    for digit in range(digits):
        # Initialize 10 buckets (0-9), each bucket stores elements with the same current digit
        buckets = [[] for _ in range(10)]

        # Distribute elements into corresponding buckets based on the current digit
        for num in arr:
            # Get the current digit: (num // 10^digit) % 10
            current_digit = (num // (10 ** digit)) % 10
            buckets[current_digit].append(num)

        # Collect elements from all buckets in order and update the array to the result after sorting for the current digit
        arr = []
        for bucket in buckets:
            arr.extend(bucket)

    return arr

Code Explanation¶

1. Handle Empty Array: If the input array is empty, return an empty array directly to avoid subsequent calculation errors.
2. Determine the Number of Digits: Use max(arr) to find the maximum number, then len(str(max_num)) to calculate its number of digits (e.g., 802 has 3 digits).
3. Bucket Distribution and Collection:
   - Initialize Buckets: Create 10 empty lists (corresponding to digits 0-9) to store elements after sorting for each digit.
   - Distribute by Digit: Iterate through each number in the array, use (num // (10 ** digit)) % 10 to get the current digit (e.g., for 170, the 0th digit (units place) is 170//1 %10=0, and the 1st digit (tens place) is 170//10 %10=7), then place the number into the corresponding bucket.
   - Collect Elements: Connect elements from all buckets in order to get the array after sorting for the current digit, which serves as input for sorting the next digit.

Test Example¶

Take the array [170, 45, 75, 90, 802, 24, 2, 66] to verify the algorithm:
1. Process Units Place (Digit 0): The units digits of all numbers are 0,5,5,0,2,2,4,6. After distributing into buckets and collecting, the result is [170, 90, 802, 2, 24, 45, 75, 66].
2. Process Tens Place (Digit 1): The tens digits of all numbers are 7,9,0,0,2,4,7,6. After distributing into buckets and collecting, the result is [802, 2, 24, 45, 66, 170, 75, 90].
3. Process Hundreds Place (Digit 2): The hundreds digits of all numbers are 8,0,0,0,0,1,0,0. After distributing into buckets and collecting, the result is [2, 24, 45, 66, 75, 90, 170, 802], and the sorting is complete.

Summary¶

Radix Sort achieves sorting by distributing and collecting elements by digits. Its time complexity is O(d × (n + k)), where d is the number of digits of the largest number, n is the array length, and k is the number of buckets (here k=10). It is particularly suitable for sorting integer arrays with fewer digits, and is more efficient when there are repeated numbers in the array. To handle negative numbers, first convert negative numbers to positive numbers, sort, and then restore the signs.