Когда мы должны использовать Radix sort?

Сортировку по радиусу труднее обобщить, чем большинство других алгоритмов сортировки. Для этого требуются ключи фиксированного размера и какой-то стандартный способ разбивания ключей на части. Таким образом, она никогда не находит своего пути в библиотеки.

Отредактировано в соответствии с вашими комментариями:

• сортировка по Радиксу применяется только к целым числам, строкам фиксированного размера, плавающим точкам и к предикатам сравнения" меньше"," больше "или" лексикографический порядок", тогда как сортировка по сравнению может принимать различные порядки.
• k может быть больше логарифма N.
• быстрая сортировка может быть выполнена на месте, сортировка по радиусу становится менее эффективной.

Когда n > 128, мы должны использовать RadixSort

При сортировке int32s я выбираю radix 256, поэтому k = log(256, 2^32) = 4, которая значительно меньше log (2, n)

И в моем тесте сортировка radix в лучшем случае в 7 раз быстрее, чем quicksort.

public class RadixSort {
    private static final int radix=256, shifts[]={8,16,24}, mask=radix-1;
    private final int bar[]=new int[radix];
    private int s[] = new int[65536];//不使用额外的数组t，提高cpu的cache命中率

    public void ensureSort(int len){
        if(s.length < len)
            s = new int[len];
    }   

    public void sort(int[] a){
        int n=a.length;
        ensureSort(n);
        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[a[i]&mask]++;//bar存放了桶内元素数量
        for(int i=1;i<radix;i++)bar[i]+=bar[i-1];//bar存放了桶内的各个元素在排序结果中的最大下标+1
        for(int i=0;i<n;i++)s[--bar[a[i]&mask]]=a[i];//对桶内元素，在bar中找到下标x=bar[slot]-1, 另s[x]=a[i]（同时--bar[slot]将下标前移，供桶内其它元素使用）

        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[(s[i]>>8)&mask]++;
        for(int i=1;i<radix;i++)bar[i]+=bar[i-1];
        for(int i=n-1;i>=0;i--)a[--bar[(s[i]>>8)&mask]]=s[i];//同一个桶内的元素，低位已排序，而放入t中时是从t的大下标向小下标放入的，所以应该逆序遍历s[i]来保证原有的顺序不变

        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[(a[i]>>16)&mask]++;
        for(int i=1;i<radix;i++)bar[i]+=bar[i-1];
        for(int i=n-1;i>=0;i--)s[--bar[(a[i]>>16)&mask]]=a[i];//同一个桶内的元素，低位已排序，而放入t中时是从t的大下标向小下标放入的，所以应该逆序遍历s[i]来保证原有的顺序不变

        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[(s[i]>>24)&mask]++;
        for(int i=129;i<radix;i++)bar[i]+=bar[i-1];//bar[128~255]是负数，比正数小
        bar[0] += bar[255];
        for(int i=1;i<128;i++)bar[i]+=bar[i-1];     
        for(int i=n-1;i>=0;i--)a[--bar[(s[i]>>24)&mask]]=s[i];//同一个桶内的元素，低位已排序，而放入t中时是从t的大下标向小下标放入的，所以应该逆序遍历s[i]来保证原有的顺序不变      
    }
}

Если у вас нет огромного списка или чрезвычайно маленьких ключей, log(N) обычно меньше k, но редко намного выше. Таким образом, выбор алгоритма сортировки общего назначения с O(N log N) средней производительностью не обязательно хуже, чем использование сортировки по радиксу.

Поправка : Как указал @Mehrdad в комментариях, аргумент выше не звучит: либо размер ключа постоянен, то сортировка по радиксу-O(N), либо размер ключа-k, то quicksort-O (k N log N). Так что в теории, radix sort действительно имеет лучшее асимптотическое время выполнения.

На практике во времени выполнения будут преобладать такие термины, как:

• Вид радикса: c1 k N

• Quicksort: C2 k N log (N)

Где c1 > > c2, потому что "извлечение" битов из более длинного ключа обычно является дорогостоящей операцией, включающей битовые сдвиги и логические операции (или, по крайней мере, доступ к памяти без выравнивания), в то время как современные процессоры могут сравнивать ключи с 64, 128 или даже 256 битами в одной операции. Так для многих распространенных случаев, если N не является гигантским, c1 будет больше, чем C2 log (N)

Другие ответы здесь ужасны, они не дают примеров, когда вид radix фактически используется.

Примером может служить создание "массива суффиксов" с использованием алгоритма skew DC3 (Kärkkäinen-Sanders-Burkhardt). Алгоритм является только линейно-временным, если алгоритм сортировки является линейно-временным, и сортировка по радиксу необходима и полезна здесь, потому что ключи коротки по конструкции (3-кортежи целых чисел).

Сортировка по Радиксу занимает O (k*n) времени. Но вы должны спросить, Что такое К. К. - Это "число цифр" (немного упрощенно, но в основном что-то вроде этого).

Итак, сколько у вас цифр? Вполне ответ, больше, чем log(n) (log с использованием "размера цифры" в качестве базы), что делает алгоритм Radix o(n log n).

Почему это? Если у вас меньше логарифмических(n) цифр, то у вас меньше n возможных чисел. Следовательно, вы можете просто использовать "count sort", который занимает O (n) времени (просто посчитайте, сколько из каждый номер у вас есть). Поэтому я предполагаю, что у вас есть больше, чем k>log(n) цифр...

Вот почему люди не используют Radix sort так много. Хотя есть случаи, когда его стоит использовать, в большинстве случаев быстрая сортировка намного лучше.

K = "длина самого длинного значения в массиве, подлежащего сортировке"

N = "длина массива"

O (k*n) = "худший вариант выполнения"

K * n = n^2 (Если k = n)

Поэтому при использовании сортировки по радиусу убедитесь, что" самое длинное целое число короче размера массива " или наоборот. Тогда ты победишь зыбучую корку!

Недостаток заключается в том, что большую часть времени вы не можете гарантировать, насколько большими становятся целые числа, но если у вас есть фиксированный диапазон чисел, сортировка по радиксу должна быть способом пойти.

Вот ссылка, которая сравнивает quicksort и radixsort:

Является ли сортировка radix более быстрой, чем quicksort для целых массивов? (Да, это так, 2-3x)

Вот еще одна ссылка, которая анализирует время работы нескольких алгоритмов:

Своего рода Вопрос :

Что быстрее на тех же данных; сортировка O(n) или сортировка O(nLog(n))?

Ответ: это зависит. Это зависит от объема сортируемых данных. Это зависит от оборудования, на котором он выполняется, и это зависит от реализации алгоритмов.

Radix sort не является сортировкой на основе сравнения и может сортировать только числовые типы, такие как целые числа (включая адреса указателей) и с плавающей запятой, и немного трудно переносить поддержку с плавающей запятой.

Вероятно, это связано с тем, что он имеет такой узкий диапазон применимости, что многие стандартные библиотеки предпочитают его опускать. Он даже не может позволить вам предоставить свой собственный компаратор, так как некоторые люди могут даже не хотеть сортировать целые числа напрямую, а использовать целые числа в качестве индексов к чему-то еще можно использовать в качестве ключа для сортировки, например, основанные на сравнении сорта позволяют всю эту гибкость, так что, вероятно, это случай просто предпочтения обобщенного решения, соответствующего 99% ежедневных потребностей людей, вместо того, чтобы идти из пути, чтобы удовлетворить этот 1%. Тем не менее, несмотря на узкую применимость, в моей области я нахожу больше пользы для сортов radix, чем для интросортов или quicksorts. Я нахожусь в этом 1% и почти никогда не работаю, скажем, со строковыми ключами, но часто нахожу варианты использования для чисел, которые выигрывают от сортировка. Дело в том, что моя кодовая база вращается вокруг индексов сущностей и компонентов (entity-component system), а также таких вещей, как индексированные сетки, и есть много числовых данных. В результате, radix sort становится полезным для всех видов вещей в моем случае. Один из распространенных примеров в моем случае-устранение дубликатов индексов. В этом случае мне действительно не нужно сортировать результаты, но часто сортировка по радиксу может устранить дубликаты быстрее, чем альтернативы. Другой - найти, скажем, медианное расщепление для KD-дерева вдоль заданного измерения. Там radix сортировка значений с плавающей запятой точки для данного измерения дает мне среднюю позицию быстро в линейное время, чтобы разделить узел дерева.

Другой-это глубинная сортировка примитивов более высокого уровня по z для полупристойной Альфа-прозрачности, если мы не собираемся делать это в шейдере frag. Это также относится к GUIs и векторной графике программного обеспечения для z-порядка элементы.

Другой-удобный для кэша последовательный доступ с использованием списка индексов. Если индексы проходят много раз, это часто улучшает производительность, если я сортирую их заранее, так что обход выполняется в последовательном порядке, а не в случайном порядке. Последний мог зигзагообразно двигаться вперед и назад в памяти, вытесняя данные из строк кэша только для повторной загрузки одной и той же области памяти в одном и том же цикле. Когда я радиксом сортирую индексы сначала, прежде чем обращаться к ним повторно, это перестает происходить и я могу значительно уменьшить промахи кэша. Это на самом деле мое самое распространенное использование для сортировки radix, и это ключ к тому, чтобы мои ECS были кэш-дружественными, когда системы хотят получить доступ к сущностям с двумя или более компонентами.

В моем случае у меня есть многопоточный вид radix, который я использую довольно часто. Некоторые контрольные показатели:

--------------------------------------------
- test_mt_sort
--------------------------------------------
Sorting 1,000,000 elements 32 times...

mt_radix_sort: {0.234000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

std::sort: {1.778000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

qsort: {2.730000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

Я могу усреднить что-то вроде 6-7 мс, чтобы отсортировать миллион чисел один раз на моем Динки аппаратном обеспечении, которое не так быстро, как я хотел бы, так как 6-7 миллисекунд могут все еще заметен пользователями иногда в интерактивных контекстах, но все еще намного лучше, чем 55-85 МС, как в случае C++std::sort или C qsort, что определенно приведет к очень очевидным сбоям в частоте кадров. Я даже слышал о людях, которые реализовывали виды радикса с помощью SIMD, хотя я понятия не имею, как им это удалось. Я недостаточно умен, чтобы придумать такое решение, хотя даже мой наивный маленький вид radix делает довольно хорошо по сравнению со стандартными библиотеками.

Одним из примеров может быть сортировка очень большого набора или массива целых чисел. Сортировка по радиксу и любые другие типы сортировок распределения чрезвычайно быстры, так как элементы данных в основном помещаются в очередь в массив очередей (максимум 10 очередей для сортировки по радиксу LSD) и переназначаются в другое расположение индекса тех же входных данных, которые будут отсортированы. Здесь нет вложенных циклов, поэтому алгоритм имеет тенденцию вести себя более линейно, так как число входных целых чисел, подлежащих сортировке, становится значительно больше. В отличие от других методов сортировки, таких как крайне неэффективный метод bubbleSort, метод radix sort не реализует операции сравнения для сортировки. Это просто простой процесс перестановки целых чисел в разные позиции индекса, пока входные данные не будут окончательно отсортированы. Если вы хотите протестировать LSD radix sort для себя, я написал один из них и сохранил на github, который можно легко протестировать на онлайн-среде JS ide, такой как Eloquent javascript coding sandbox. Не стесняйтесь играть с ним и смотреть как он ведет себя с различными числами n. я протестировал до 900 000 несортированных целых чисел с временем выполнения

Https://gist.github.com/StBean/4af58d09021899f14dfa585df6c86df6