Сортировка — фундаментальная операция в информатике, и за прошедшие годы были разработаны различные алгоритмы сортировки. Одним из таких алгоритмов является поразрядная сортировка, которая обеспечивает линейную временную сложность за счет распределения элементов по сегментам на основе их цифр или символов. В этой статье мы рассмотрим различные методы реализации поразрядной сортировки в Golang, попутно предоставляя примеры кода.

Метод 1: поразрядная сортировка по наименьшему значащему разряду (LSD)
Поразрядная сортировка по наименьшему значащему разряду (LSD) является наиболее распространенным вариантом поразрядной сортировки. Он начинается с рассмотрения младшей значащей цифры каждого элемента и сортирует элементы на основе этой цифры. Затем он переходит к следующей значащей цифре, пока не будут учтены все цифры. Вот пример реализации в Golang:

func radixSortLSD(arr []int) []int {
    max := getMax(arr)
    for exp := 1; max/exp > 0; exp *= 10 {
        count := make([]int, 10)
        result := make([]int, len(arr))
        for i := 0; i < len(arr); i++ {
            count[(arr[i]/exp)%10]++
        }
        for i := 1; i < 10; i++ {
            count[i] += count[i-1]
        }
        for i := len(arr) - 1; i >= 0; i-- {
            result[count[(arr[i]/exp)%10]-1] = arr[i]
            count[(arr[i]/exp)%10]--
        }
        copy(arr, result)
    }
    return arr
}

Метод 2: Поразрядная сортировка по наиболее значимому разряду (MSD)
Поразрядная сортировка по наиболее значимому разряду (MSD) начинается с рассмотрения наиболее значимой цифры каждого элемента и рекурсивно применяет поразрядную сортировку к каждой группе элементов, имеющих одинаковое наибольшее число элементов. значащая цифра. Вот пример реализации в Golang:

func radixSortMSD(arr []int) []int {
    max := getMax(arr)
    return radixSortMSDHelper(arr, max)
}
func radixSortMSDHelper(arr []int, exp int) []int {
    if exp <= 0 {
        return arr
    }
    count := make([]int, 10)
    result := make([]int, len(arr))
    for i := 0; i < len(arr); i++ {
        count[(arr[i]/exp)%10]++
    }
    for i := 1; i < 10; i++ {
        count[i] += count[i-1]
    }
    for i := len(arr) - 1; i >= 0; i-- {
        result[count[(arr[i]/exp)%10]-1] = arr[i]
        count[(arr[i]/exp)%10]--
    }
    copy(arr, result)
    for i := 0; i < 10; i++ {
        start := 0
        for j := 0; j < len(arr); j++ {
            if (arr[j]/exp)%10 == i {
                arr[start], arr[j] = arr[j], arr[start]
                start++
            }
        }
        if start > 1 {
            radixSortMSDHelper(arr[:start], exp/10)
        }
    }
    return arr
}

Поразрядная сортировка – это мощный алгоритм сортировки, позволяющий эффективно обрабатывать большие наборы данных с разной длиной цифр. В этой статье мы исследовали два распространенных метода реализации поразрядной сортировки в Golang: поразрядную сортировку LSD и поразрядную сортировку MSD. В зависимости от характеристик ваших данных вы можете выбрать наиболее подходящий вариант для достижения оптимальной производительности. Понимая и используя эти методы сортировки, вы можете повысить эффективность своего кода при решении крупномасштабных задач сортировки.