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

Ответ 1

Быстрая сортировка имеет среднее значение O (N logN), но она также имеет наихудший случай O (N ^ 2), поэтому даже в большинстве практических случаев она не попадает в N ^ 2, всегда существует риск что вход будет в "плохом порядке" для вас. Этот риск не существует в сортировке radix. Я думаю, что это дает большое преимущество для сортировки radix.

Ответ 2

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

Ответ 3

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

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

Ответ 4

когда 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]来保证原有的顺序不变      
    }
}

Ответ 5

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

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

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

• сортировка radix: c1 k N

• quicksort: c2 k N log (N)

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

Ответ 6

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

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

Ответ 7

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

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

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

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

Ответ 8

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

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

O (k * n) = "наихудший ход"

k * n = n ^ 2 (если k = n)

поэтому при использовании сортировки Radix убедитесь, что "самое длинное целое число меньше размера массива" или наоборот. Затем вы будете бить Quicksort!

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

Ответ 9

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

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

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

Вопрос о сортировках:

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

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

Ответ 10

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

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