---

[!info] related notes 算法面试题型 MOC 排序算法总结

Radix Sort (LSD)

Radix sort is a non-comparison sorting algorithm.

When It Applies

• Works best when keys are integers (or fixed-length strings) and you can extract digits.
• Typical constraint: non-negative integers.
• If negatives exist: common trick is to shift all numbers by -minValue to make them non-negative, sort, then shift back.

Key Idea

• Sort by least-significant digit to most-significant digit.
• Each digit pass is a stable counting sort.
• The “prefix-count” (cumulative counts) converts frequency counts into stable positions.

Complexity

• Time: O(n * d) where d is number of digits (or passes)
• Extra space: O(n + base)

Template (Java, base-10)

import java.util.Arrays;

public class RadixSort {
    private static final int BASE = 10;

    public static void radixSortNonNegative(int[] arr) {
        if (arr == null || arr.length < 2) return;

        int n = arr.length;
        int max = 0;
        for (int v : arr) max = Math.max(max, v);

        int[] help = new int[n];
        int[] cnts = new int[BASE];

        for (int offset = 1; max / offset > 0; offset *= BASE) {
            Arrays.fill(cnts, 0);
            for (int v : arr) {
                int digit = (v / offset) % BASE;
                cnts[digit]++;
            }
            for (int i = 1; i < BASE; i++) {
                cnts[i] += cnts[i - 1];
            }
            // stable: iterate from right to left
            for (int i = n - 1; i >= 0; i--) {
                int digit = (arr[i] / offset) % BASE;
                help[--cnts[digit]] = arr[i];
            }
            System.arraycopy(help, 0, arr, 0, n);
        }
    }

    public static void radixSort(int[] arr) {
        if (arr == null || arr.length < 2) return;

        int min = arr[0];
        for (int v : arr) min = Math.min(min, v);
        if (min < 0) {
            for (int i = 0; i < arr.length; i++) arr[i] -= min;
            radixSortNonNegative(arr);
            for (int i = 0; i < arr.length; i++) arr[i] += min;
        } else {
            radixSortNonNegative(arr);
        }
    }
}

Related

• 快速排序
• 堆与堆排序