Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

# 11.10 Поразрядная сортировка

В предыдущем разделе была рассмотрена сортировка подсчетом: она хорошо подходит для случаев, когда объем данных \(n\) велик, а диапазон значений \(m\) сравнительно мал. Предположим теперь, что нужно отсортировать \(n = 10^6\) номеров студентов, причем каждый номер представляет собой \(8\)-значное число. Тогда диапазон данных \(m = 10^8\) оказывается очень большим. Сортировка подсчетом потребует огромного объема памяти, а поразрядная сортировка позволяет этого избежать.

Поразрядная сортировка (radix sort) по своей основной идее совпадает с сортировкой подсчетом и тоже реализует сортировку через подсчет количества. При этом поразрядная сортировка использует соотношение между разрядами числа и последовательно сортирует данные по каждому разряду, получая итоговый упорядоченный результат.

## 11.10.1 Алгоритм

Рассмотрим пример со студенческими номерами: будем считать, что младший разряд имеет номер \(1\) , а старший - номер \(8\) . Тогда процесс поразрядной сортировки показан на рисунке 11-18.

1. Инициализировать номер разряда \(k = 1\) .
2. Выполнить «сортировку подсчетом» по \(k\)-му разряду студенческого номера. После этого данные будут упорядочены по \(k\)-му разряду по возрастанию.
3. Увеличить \(k\) на \(1\) и вернуться к шагу `2.` , продолжая процесс, пока сортировка не будет выполнена для всех разрядов.

Рисунок 11-18 Процесс поразрядной сортировки

Ниже разберем реализацию кода. Для числа \(x\) в системе счисления с основанием \(d\) получить его \(k\)-й разряд \(x_k\) можно по формуле:

\[ x_k = \lfloor\frac{x}{d^{k-1}}\rfloor \bmod d \]

где \(\lfloor a \rfloor\) обозначает округление числа \(a\) вниз, а \(\bmod \: d\) означает взятие остатка по модулю \(d\) . Для студенческих номеров выполняется \(d = 10\) и \(k \in [1, 8]\) .

Кроме того, нам нужно слегка изменить код сортировки подсчетом, чтобы он мог сортировать числа по их \(k\)-му разряду:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
radix_sort.py

    def digit(num: int, exp: int) -> int:
        """Получить k-й разряд элемента num, где exp = 10^(k-1)"""
        # Передача exp вместо k позволяет избежать повторного дорогостоящего вычисления степени
        return (num // exp) % 10

    def counting_sort_digit(nums: list[int], exp: int):
        """Сортировка подсчетом (сортировка по k-му разряду nums)"""
        # Разряды десятичной системы лежат в диапазоне 0~9, поэтому нужен массив корзин длины 10
        counter = [0] * 10
        n = len(nums)
        # Подсчитать число появлений каждой цифры от 0 до 9
        for i in range(n):
            d = digit(nums[i], exp)  # Получить k-й разряд nums[i], обозначив его как d
            counter[d] += 1  # Подсчитать число появлений цифры d
        # Вычислить префиксные суммы и преобразовать «число появлений» в «индекс массива»
        for i in range(1, 10):
            counter[i] += counter[i - 1]
        # Выполняя обратный проход, заполнить res элементами по статистике в корзинах
        res = [0] * n
        for i in range(n - 1, -1, -1):
            d = digit(nums[i], exp)
            j = counter[d] - 1  # Получить индекс j цифры d в массиве
            res[j] = nums[i]  # Поместить текущий элемент по индексу j
            counter[d] -= 1  # Уменьшить количество d на 1
        # Перезаписать исходный массив nums результатом
        for i in range(n):
            nums[i] = res[i]

    def radix_sort(nums: list[int]):
        """Поразрядная сортировка"""
        # Получить максимальный элемент массива, чтобы определить максимальное число разрядов
        m = max(nums)
        # Проходить разряды от младшего к старшему
        exp = 1
        while exp <= m:
            # Выполнить сортировку подсчетом по k-му разряду элементов массива
            # k = 1 -> exp = 1
            # k = 2 -> exp = 10
            # то есть exp = 10^(k-1)
            counting_sort_digit(nums, exp)
            exp *= 10

radix_sort.cpp

    /* Получить k-й разряд элемента num, где exp = 10^(k-1) */
    int digit(int num, int exp) {
        // Передача exp вместо k позволяет избежать повторного дорогостоящего вычисления степени
        return (num / exp) % 10;
    }

    /* Сортировка подсчетом (сортировка по k-му разряду nums) */
    void countingSortDigit(vector<int> &nums, int exp) {
        // Разряды десятичной системы лежат в диапазоне 0~9, поэтому нужен массив корзин длины 10
        vector<int> counter(10, 0);
        int n = nums.size();
        // Подсчитать число появлений каждой цифры от 0 до 9
        for (int i = 0; i < n; i++) {
            int d = digit(nums[i], exp); // Получить k-й разряд nums[i], обозначив его как d
            counter[d]++;                // Подсчитать число появлений цифры d
        }
        // Вычислить префиксные суммы и преобразовать «число появлений» в «индекс массива»
        for (int i = 1; i < 10; i++) {
            counter[i] += counter[i - 1];
        }
        // Выполняя обратный проход, заполнить res элементами по статистике в корзинах
        vector<int> res(n, 0);
        for (int i = n - 1; i >= 0; i--) {
            int d = digit(nums[i], exp);
            int j = counter[d] - 1; // Получить индекс j цифры d в массиве
            res[j] = nums[i];       // Поместить текущий элемент по индексу j
            counter[d]--;           // Уменьшить количество d на 1
        }
        // Перезаписать исходный массив nums результатом
        for (int i = 0; i < n; i++)
            nums[i] = res[i];
    }

    /* Поразрядная сортировка */
    void radixSort(vector<int> &nums) {
        // Получить максимальный элемент массива, чтобы определить максимальное число разрядов
        int m = *max_element(nums.begin(), nums.end());
        // Проходить разряды от младшего к старшему
        for (int exp = 1; exp <= m; exp *= 10)
            // Выполнить сортировку подсчетом по k-му разряду элементов массива
            // k = 1 -> exp = 1
            // k = 2 -> exp = 10
            // то есть exp = 10^(k-1)
            countingSortDigit(nums, exp);
    }

radix_sort.java

    /* Получить k-й разряд элемента num, где exp = 10^(k-1) */
    int digit(int num, int exp) {
        // Передача exp вместо k позволяет избежать повторного дорогостоящего вычисления степени
        return (num / exp) % 10;
    }

    /* Сортировка подсчетом (сортировка по k-му разряду nums) */
    void countingSortDigit(int[] nums, int exp) {
        // Разряды десятичной системы лежат в диапазоне 0~9, поэтому нужен массив корзин длины 10
        int[] counter = new int[10];
        int n = nums.length;
        // Подсчитать число появлений каждой цифры от 0 до 9
        for (int i = 0; i < n; i++) {
            int d = digit(nums[i], exp); // Получить k-й разряд nums[i], обозначив его как d
            counter[d]++;                // Подсчитать число появлений цифры d
        }
        // Вычислить префиксные суммы и преобразовать «число появлений» в «индекс массива»
        for (int i = 1; i < 10; i++) {
            counter[i] += counter[i - 1];
        }
        // Выполняя обратный проход, заполнить res элементами по статистике в корзинах
        int[] res = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            int d = digit(nums[i], exp);
            int j = counter[d] - 1; // Получить индекс j цифры d в массиве
            res[j] = nums[i];       // Поместить текущий элемент по индексу j
            counter[d]--;           // Уменьшить количество d на 1
        }
        // Перезаписать исходный массив nums результатом
        for (int i = 0; i < n; i++)
            nums[i] = res[i];
    }

    /* Поразрядная сортировка */
    void radixSort(int[] nums) {
        // Получить максимальный элемент массива, чтобы определить максимальное число разрядов
        int m = Integer.MIN_VALUE;
        for (int num : nums)
            if (num > m)
                m = num;
        // Проходить разряды от младшего к старшему
        for (int exp = 1; exp <= m; exp *= 10) {
            // Выполнить сортировку подсчетом по k-му разряду элементов массива
            // k = 1 -> exp = 1
            // k = 2 -> exp = 10
            // то есть exp = 10^(k-1)
            countingSortDigit(nums, exp);
        }
    }

radix_sort.cs

    /* Получить k-й разряд элемента num, где exp = 10^(k-1) */
    int Digit(int num, int exp) {
        // Передача exp вместо k позволяет избежать повторного дорогостоящего вычисления степени
        return (num / exp) % 10;
    }

    /* Сортировка подсчетом (сортировка по k-му разряду nums) */
    void CountingSortDigit(int[] nums, int exp) {
        // Разряды десятичной системы лежат в диапазоне 0~9, поэтому нужен массив корзин длины 10
        int[] counter = new int[10];
        int n = nums.Length;
        // Подсчитать число появлений каждой цифры от 0 до 9
        for (int i = 0; i < n; i++) {
            int d = Digit(nums[i], exp); // Получить k-й разряд nums[i], обозначив его как d
            counter[d]++;                // Подсчитать число появлений цифры d
        }
        // Вычислить префиксные суммы и преобразовать «число появлений» в «индекс массива»
        for (int i = 1; i < 10; i++) {
            counter[i] += counter[i - 1];
        }
        // Выполняя обратный проход, заполнить res элементами по статистике в корзинах
        int[] res = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            int d = Digit(nums[i], exp);
            int j = counter[d] - 1; // Получить индекс j цифры d в массиве
            res[j] = nums[i];       // Поместить текущий элемент по индексу j
            counter[d]--;           // Уменьшить количество d на 1
        }
        // Перезаписать исходный массив nums результатом
        for (int i = 0; i < n; i++) {
            nums[i] = res[i];
        }
    }

    /* Поразрядная сортировка */
    void RadixSort(int[] nums) {
        // Получить максимальный элемент массива, чтобы определить максимальное число разрядов
        int m = int.MinValue;
        foreach (int num in nums) {
            if (num > m) m = num;
        }
        // Проходить разряды от младшего к старшему
        for (int exp = 1; exp <= m; exp *= 10) {
            // Выполнить сортировку подсчетом по k-му разряду элементов массива
            // k = 1 -> exp = 1
            // k = 2 -> exp = 10
            // то есть exp = 10^(k-1)
            CountingSortDigit(nums, exp);
        }
    }

radix_sort.go

    /* Получить k-й разряд элемента num, где exp = 10^(k-1) */
    func digit(num, exp int) int {
        // Передача exp вместо k позволяет избежать повторного дорогостоящего вычисления степени
        return (num / exp) % 10
    }

    /* Сортировка подсчетом (сортировка по k-му разряду nums) */
    func countingSortDigit(nums []int, exp int) {
        // Разряды десятичной системы лежат в диапазоне 0~9, поэтому нужен массив корзин длины 10
        counter := make([]int, 10)
        n := len(nums)
        // Подсчитать число появлений каждой цифры от 0 до 9
        for i := 0; i < n; i++ {
            d := digit(nums[i], exp) // Получить k-й разряд nums[i], обозначив его как d
            counter[d]++             // Подсчитать число появлений цифры d
        }
        // Вычислить префиксные суммы и преобразовать «число появлений» в «индекс массива»
        for i := 1; i < 10; i++ {
            counter[i] += counter[i-1]
        }
        // Выполняя обратный проход, заполнить res элементами по статистике в корзинах
        res := make([]int, n)
        for i := n - 1; i >= 0; i-- {
            d := digit(nums[i], exp)
            j := counter[d] - 1 // Получить индекс j цифры d в массиве
            res[j] = nums[i]    // Поместить текущий элемент по индексу j
            counter[d]--        // Уменьшить количество d на 1
        }
        // Перезаписать исходный массив nums результатом
        for i := 0; i < n; i++ {
            nums[i] = res[i]
        }
    }

    /* Поразрядная сортировка */
    func radixSort(nums []int) {
        // Получить максимальный элемент массива, чтобы определить максимальное число разрядов
        max := math.MinInt
        for _, num := range nums {
            if num > max {
                max = num
            }
        }
        // Проходить разряды от младшего к старшему
        for exp := 1; max >= exp; exp *= 10 {
            // Выполнить сортировку подсчетом по k-му разряду элементов массива
            // k = 1 -> exp = 1
            // k = 2 -> exp = 10
            // то есть exp = 10^(k-1)
            countingSortDigit(nums, exp)
        }
    }

radix_sort.swift

    /* Получить k-й разряд элемента num, где exp = 10^(k-1) */
    func digit(num: Int, exp: Int) -> Int {
        // Передача exp вместо k позволяет избежать повторного дорогостоящего вычисления степени
        (num / exp) % 10
    }

    /* Сортировка подсчетом (сортировка по k-му разряду nums) */
    func countingSortDigit(nums: inout [Int], exp: Int) {
        // Разряды десятичной системы лежат в диапазоне 0~9, поэтому нужен массив корзин длины 10
        var counter = Array(repeating: 0, count: 10)
        // Подсчитать число появлений каждой цифры от 0 до 9
        for i in nums.indices {
            let d = digit(num: nums[i], exp: exp) // Получить k-й разряд nums[i], обозначив его как d
            counter[d] += 1 // Подсчитать число появлений цифры d
        }
        // Вычислить префиксные суммы и преобразовать «число появлений» в «индекс массива»
        for i in 1 ..< 10 {
            counter[i] += counter[i - 1]
        }
        // Выполняя обратный проход, заполнить res элементами по статистике в корзинах
        var res = Array(repeating: 0, count: nums.count)
        for i in nums.indices.reversed() {
            let d = digit(num: nums[i], exp: exp)
            let j = counter[d] - 1 // Получить индекс j цифры d в массиве
            res[j] = nums[i] // Поместить текущий элемент по индексу j
            counter[d] -= 1 // Уменьшить количество d на 1
        }
        // Перезаписать исходный массив nums результатом
        for i in nums.indices {
            nums[i] = res[i]
        }
    }

    /* Поразрядная сортировка */
    func radixSort(nums: inout [Int]) {
        // Получить максимальный элемент массива, чтобы определить максимальное число разрядов
        var m = Int.min
        for num in nums {
            if num > m {
                m = num
            }
        }
        // Проходить разряды от младшего к старшему
        for exp in sequence(first: 1, next: { m >= ($0 * 10) ? $0 * 10 : nil }) {
            // Выполнить сортировку подсчетом по k-му разряду элементов массива
            // k = 1 -> exp = 1
            // k = 2 -> exp = 10
            // то есть exp = 10^(k-1)
            countingSortDigit(nums: &nums, exp: exp)
        }
    }

radix_sort.js

    /* Получить k-й разряд элемента num, где exp = 10^(k-1) */
    function digit(num, exp) {
        // Передача exp вместо k позволяет избежать повторного дорогостоящего вычисления степени
        return Math.floor(num / exp) % 10;
    }

    /* Сортировка подсчетом (сортировка по k-му разряду nums) */
    function countingSortDigit(nums, exp) {
        // Разряды десятичной системы лежат в диапазоне 0~9, поэтому нужен массив корзин длины 10
        const counter = new Array(10).fill(0);
        const n = nums.length;
        // Подсчитать число появлений каждой цифры от 0 до 9
        for (let i = 0; i < n; i++) {
            const d = digit(nums[i], exp); // Получить k-й разряд nums[i], обозначив его как d
            counter[d]++; // Подсчитать число появлений цифры d
        }
        // Вычислить префиксные суммы и преобразовать «число появлений» в «индекс массива»
        for (let i = 1; i < 10; i++) {
            counter[i] += counter[i - 1];
        }
        // Выполняя обратный проход, заполнить res элементами по статистике в корзинах
        const res = new Array(n).fill(0);
        for (let i = n - 1; i >= 0; i--) {
            const d = digit(nums[i], exp);
            const j = counter[d] - 1; // Получить индекс j цифры d в массиве
            res[j] = nums[i]; // Поместить текущий элемент по индексу j
            counter[d]--; // Уменьшить количество d на 1
        }
        // Перезаписать исходный массив nums результатом
        for (let i = 0; i < n; i++) {
            nums[i] = res[i];
        }
    }

    /* Поразрядная сортировка */
    function radixSort(nums) {
        // Получить максимальный элемент массива, чтобы определить максимальное число разрядов
        let m = Math.max(... nums);
        // Проходить разряды от младшего к старшему
        for (let exp = 1; exp <= m; exp *= 10) {
            // Выполнить сортировку подсчетом по k-му разряду элементов массива
            // k = 1 -> exp = 1
            // k = 2 -> exp = 10
            // то есть exp = 10^(k-1)
            countingSortDigit(nums, exp);
        }
    }

radix_sort.ts

    /* Получить k-й разряд элемента num, где exp = 10^(k-1) */
    function digit(num: number, exp: number): number {
        // Передача exp вместо k позволяет избежать повторного дорогостоящего вычисления степени
        return Math.floor(num / exp) % 10;
    }

    /* Сортировка подсчетом (сортировка по k-му разряду nums) */
    function countingSortDigit(nums: number[], exp: number): void {
        // Разряды десятичной системы лежат в диапазоне 0~9, поэтому нужен массив корзин длины 10
        const counter = new Array(10).fill(0);
        const n = nums.length;
        // Подсчитать число появлений каждой цифры от 0 до 9
        for (let i = 0; i < n; i++) {
            const d = digit(nums[i], exp); // Получить k-й разряд nums[i], обозначив его как d
            counter[d]++; // Подсчитать число появлений цифры d
        }
        // Вычислить префиксные суммы и преобразовать «число появлений» в «индекс массива»
        for (let i = 1; i < 10; i++) {
            counter[i] += counter[i - 1];
        }
        // Выполняя обратный проход, заполнить res элементами по статистике в корзинах
        const res = new Array(n).fill(0);
        for (let i = n - 1; i >= 0; i--) {
            const d = digit(nums[i], exp);
            const j = counter[d] - 1; // Получить индекс j цифры d в массиве
            res[j] = nums[i]; // Поместить текущий элемент по индексу j
            counter[d]--; // Уменьшить количество d на 1
        }
        // Перезаписать исходный массив nums результатом
        for (let i = 0; i < n; i++) {
            nums[i] = res[i];
        }
    }

    /* Поразрядная сортировка */
    function radixSort(nums: number[]): void {
        // Получить максимальный элемент массива, чтобы определить максимальное число разрядов
        let m: number = Math.max(... nums);
        // Проходить разряды от младшего к старшему
        for (let exp = 1; exp <= m; exp *= 10) {
            // Выполнить сортировку подсчетом по k-му разряду элементов массива
            // k = 1 -> exp = 1
            // k = 2 -> exp = 10
            // то есть exp = 10^(k-1)
            countingSortDigit(nums, exp);
        }
    }

radix_sort.dart

    /* Получить k-й разряд элемента _num, где exp = 10^(k-1) */
    int digit(int _num, int exp) {
      // Передача exp вместо k позволяет избежать повторного дорогостоящего вычисления степени
      return (_num ~/ exp) % 10;
    }

    /* Сортировка подсчетом (сортировка по k-му разряду nums) */
    void countingSortDigit(List<int> nums, int exp) {
      // Разряды десятичной системы лежат в диапазоне 0~9, поэтому нужен массив корзин длины 10
      List<int> counter = List<int>.filled(10, 0);
      int n = nums.length;
      // Подсчитать число появлений каждой цифры от 0 до 9
      for (int i = 0; i < n; i++) {
        int d = digit(nums[i], exp); // Получить k-й разряд nums[i], обозначив его как d
        counter[d]++; // Подсчитать число появлений цифры d
      }
      // Вычислить префиксные суммы и преобразовать «число появлений» в «индекс массива»
      for (int i = 1; i < 10; i++) {
        counter[i] += counter[i - 1];
      }
      // Выполняя обратный проход, заполнить res элементами по статистике в корзинах
      List<int> res = List<int>.filled(n, 0);
      for (int i = n - 1; i >= 0; i--) {
        int d = digit(nums[i], exp);
        int j = counter[d] - 1; // Получить индекс j цифры d в массиве
        res[j] = nums[i]; // Поместить текущий элемент по индексу j
        counter[d]--; // Уменьшить количество d на 1
      }
      // Перезаписать исходный массив nums результатом
      for (int i = 0; i < n; i++) nums[i] = res[i];
    }

    /* Поразрядная сортировка */
    void radixSort(List<int> nums) {
      // Получить максимальный элемент массива, чтобы определить максимальное число разрядов
      // В dart длина int составляет 64 бита
      int m = -1 << 63;
      for (int _num in nums) if (_num > m) m = _num;
      // Проходить разряды от младшего к старшему
      for (int exp = 1; exp <= m; exp *= 10)
        // Выполнить сортировку подсчетом по k-му разряду элементов массива
        // k = 1 -> exp = 1
        // k = 2 -> exp = 10
        // то есть exp = 10^(k-1)
        countingSortDigit(nums, exp);
    }

radix_sort.rs

    /* Получить k-й разряд элемента num, где exp = 10^(k-1) */
    fn digit(num: i32, exp: i32) -> usize {
        // Передача exp вместо k позволяет избежать повторного дорогостоящего вычисления степени
        return ((num / exp) % 10) as usize;
    }

    /* Сортировка подсчетом (сортировка по k-му разряду nums) */
    fn counting_sort_digit(nums: &mut [i32], exp: i32) {
        // Разряды десятичной системы лежат в диапазоне 0~9, поэтому нужен массив корзин длины 10
        let mut counter = [0; 10];
        let n = nums.len();
        // Подсчитать число появлений каждой цифры от 0 до 9
        for i in 0..n {
            let d = digit(nums[i], exp); // Получить k-й разряд nums[i], обозначив его как d
            counter[d] += 1; // Подсчитать число появлений цифры d
        }
        // Вычислить префиксные суммы и преобразовать «число появлений» в «индекс массива»
        for i in 1..10 {
            counter[i] += counter[i - 1];
        }
        // Выполняя обратный проход, заполнить res элементами по статистике в корзинах
        let mut res = vec![0; n];
        for i in (0..n).rev() {
            let d = digit(nums[i], exp);
            let j = counter[d] - 1; // Получить индекс j цифры d в массиве
            res[j] = nums[i]; // Поместить текущий элемент по индексу j
            counter[d] -= 1; // Уменьшить количество d на 1
        }
        // Перезаписать исходный массив nums результатом
        nums.copy_from_slice(&res);
    }

    /* Поразрядная сортировка */
    fn radix_sort(nums: &mut [i32]) {
        // Получить максимальный элемент массива, чтобы определить максимальное число разрядов
        let m = *nums.into_iter().max().unwrap();
        // Проходить разряды от младшего к старшему
        let mut exp = 1;
        while exp <= m {
            counting_sort_digit(nums, exp);
            exp *= 10;
        }
    }

radix_sort.c

    /* Получить k-й разряд элемента num, где exp = 10^(k-1) */
    int digit(int num, int exp) {
        // Передача exp вместо k позволяет избежать повторного дорогостоящего вычисления степени
        return (num / exp) % 10;
    }

    /* Сортировка подсчетом (сортировка по k-му разряду nums) */
    void countingSortDigit(int nums[], int size, int exp) {
        // Разряды десятичной системы лежат в диапазоне 0~9, поэтому нужен массив корзин длины 10
        int *counter = (int *)malloc((sizeof(int) * 10));
        memset(counter, 0, sizeof(int) * 10); // Инициализировать нулем для последующего освобождения памяти
        // Подсчитать число появлений каждой цифры от 0 до 9
        for (int i = 0; i < size; i++) {
            // Получить k-й разряд nums[i], обозначив его как d
            int d = digit(nums[i], exp);
            // Подсчитать число появлений цифры d
            counter[d]++;
        }
        // Вычислить префиксные суммы и преобразовать «число появлений» в «индекс массива»
        for (int i = 1; i < 10; i++) {
            counter[i] += counter[i - 1];
        }
        // Выполняя обратный проход, заполнить res элементами по статистике в корзинах
        int *res = (int *)malloc(sizeof(int) * size);
        for (int i = size - 1; i >= 0; i--) {
            int d = digit(nums[i], exp);
            int j = counter[d] - 1; // Получить индекс j цифры d в массиве
            res[j] = nums[i];       // Поместить текущий элемент по индексу j
            counter[d]--;           // Уменьшить количество d на 1
        }
        // Перезаписать исходный массив nums результатом
        for (int i = 0; i < size; i++) {
            nums[i] = res[i];
        }
        // Освободить память
        free(res);
        free(counter);
    }

    /* Поразрядная сортировка */
    void radixSort(int nums[], int size) {
        // Получить максимальный элемент массива, чтобы определить максимальное число разрядов
        int max = INT32_MIN;
        for (int i = 0; i < size; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
        }
        // Проходить разряды от младшего к старшему
        for (int exp = 1; max >= exp; exp *= 10)
            // Выполнить сортировку подсчетом по k-му разряду элементов массива
            // k = 1 -> exp = 1
            // k = 2 -> exp = 10
            // то есть exp = 10^(k-1)
            countingSortDigit(nums, size, exp);
    }

radix_sort.kt

    /* Получить k-й разряд элемента num, где exp = 10^(k-1) */
    fun digit(num: Int, exp: Int): Int {
        // Передача exp вместо k позволяет избежать повторного дорогостоящего вычисления степени
        return (num / exp) % 10
    }

    /* Сортировка подсчетом (сортировка по k-му разряду nums) */
    fun countingSortDigit(nums: IntArray, exp: Int) {
        // Разряды десятичной системы лежат в диапазоне 0~9, поэтому нужен массив корзин длины 10
        val counter = IntArray(10)
        val n = nums.size
        // Подсчитать число появлений каждой цифры от 0 до 9
        for (i in 0..<n) {
            val d = digit(nums[i], exp) // Получить k-й разряд nums[i], обозначив его как d
            counter[d]++                // Подсчитать число появлений цифры d
        }
        // Вычислить префиксные суммы и преобразовать «число появлений» в «индекс массива»
        for (i in 1..9) {
            counter[i] += counter[i - 1]
        }
        // Выполняя обратный проход, заполнить res элементами по статистике в корзинах
        val res = IntArray(n)
        for (i in n - 1 downTo 0) {
            val d = digit(nums[i], exp)
            val j = counter[d] - 1 // Получить индекс j цифры d в массиве
            res[j] = nums[i]       // Поместить текущий элемент по индексу j
            counter[d]--           // Уменьшить количество d на 1
        }
        // Перезаписать исходный массив nums результатом
        for (i in 0..<n)
            nums[i] = res[i]
    }

    /* Поразрядная сортировка */
    fun radixSort(nums: IntArray) {
        // Получить максимальный элемент массива, чтобы определить максимальное число разрядов
        var m = Int.MIN_VALUE
        for (num in nums) if (num > m) m = num
        var exp = 1
        // Проходить разряды от младшего к старшему
        while (exp <= m) {
            // Выполнить сортировку подсчетом по k-му разряду элементов массива
            // k = 1 -> exp = 1
            // k = 2 -> exp = 10
            // то есть exp = 10^(k-1)
            countingSortDigit(nums, exp)
            exp *= 10
        }
    }

radix_sort.rb

    ### Получить k-й разряд элемента num, где exp = 10^(k-1) ###
    def digit(num, exp)
      # Передача exp вместо k позволяет избежать повторного выполнения дорогостоящих вычислений степени
      (num / exp) % 10
    end

    ### Получить k-й разряд элемента num, где exp = 10^(k-1) ###
    def digit(num, exp)
      # Передача exp вместо k позволяет избежать повторного выполнения дорогостоящих вычислений степени
      (num / exp) % 10
    end

    # ## Сортировка подсчетом (сортировка по k-му разряду nums) ###
    def counting_sort_digit(nums, exp)
      # Разряды десятичной системы лежат в диапазоне 0~9, поэтому нужен массив корзин длины 10
      counter = Array.new(10, 0)
      n = nums.length
      # Подсчитать число появлений каждой цифры от 0 до 9
      for i in 0...n
        d = digit(nums[i], exp) # Получить k-й разряд nums[i], обозначив его как d
        counter[d] += 1 # Подсчитать число появлений цифры d
      end
      # Вычислить префиксные суммы и преобразовать «число появлений» в «индекс массива»
      (1...10).each { |i| counter[i] += counter[i - 1] }
      # Выполняя обратный проход, заполнить res элементами по статистике в корзинах
      res = Array.new(n, 0)
      for i in (n - 1).downto(0)
        d = digit(nums[i], exp)
        j = counter[d] - 1 # Получить индекс j цифры d в массиве
        res[j] = nums[i] # Поместить текущий элемент по индексу j
        counter[d] -= 1 # Уменьшить количество d на 1
      end
      # Перезаписать исходный массив nums результатом
      (0...n).each { |i| nums[i] = res[i] }
    end

    ### Поразрядная сортировка ###
    def radix_sort(nums)
      # Получить максимальный элемент массива, чтобы определить максимальное число разрядов
      m = nums.max
      # Проходить разряды от младшего к старшему
      exp = 1
      while exp <= m
        # Выполнить сортировку подсчетом по k-му разряду элементов массива
        # k = 1 -> exp = 1
        # k = 2 -> exp = 10
        # то есть exp = 10^(k-1)
        counting_sort_digit(nums, exp)
        exp *= 10
      end
    end

Визуализация кода

Во весь экран >

Почему сортировка выполняется от младшего разряда к старшему?

В последовательных раундах сортировки результаты более позднего раунда перекрывают результаты предыдущего. Например, если после первого раунда получилось \(a < b\) , а после второго - \(a > b\) , то именно результат второго раунда станет окончательным. Поскольку старшие разряды имеют более высокий приоритет, сначала нужно сортировать по младшим разрядам, а затем по старшим.

## 11.10.2 Характеристики алгоритма

По сравнению с сортировкой подсчетом поразрядная сортировка подходит для случаев с большим диапазоном чисел, но только при условии, что данные можно представить в виде чисел фиксированной длины и число разрядов не слишком велико. Например, числа с плавающей запятой плохо подходят для поразрядной сортировки, потому что число разрядов \(k\) слишком велико и может привести к ситуации \(O(nk) \gg O(n^2)\) .

- Временная сложность равна \(O(nk)\), алгоритм не является адаптивным: пусть объем данных равен \(n\) , числа записаны в системе счисления с основанием \(d\) , а максимальное число разрядов равно \(k\) . Тогда выполнение сортировки подсчетом для одного разряда требует \(O(n + d)\) времени, а сортировка по всем \(k\) разрядам требует \(O((n + d)k)\) времени. Обычно \(d\) и \(k\) сравнительно малы, поэтому временная сложность стремится к \(O(n)\) .
- Пространственная сложность равна \(O(n + d)\), сортировка не выполняется на месте: как и в сортировке подсчетом, здесь требуются массивы `res` и `counter` длины \(n\) и \(d\) .
- Стабильная сортировка: если сортировка подсчетом стабильна, то и поразрядная сортировка стабильна. Если же сортировка подсчетом нестабильна, поразрядная сортировка не может гарантировать корректный результат.

##### Оставляйте свои идеи, вопросы и предложения в комментариях