Самый быстрый способ сортировки массива байтов с использованием небезопасного кода?

Насколько мне известно, quicksort — один из самых быстрых алгоритмов сортировки, поскольку именно так реализована функция Array.Sort() во фреймворке. Есть ли способ ускорить сортировку массива байтов, возможно, используя небезопасный код и указатели?


c# sorting unsafe
person yq8    schedule 28.08.2016    source источник
comment
Использование примитивов более низкого уровня не увеличивает сложность алгоритма.   -  person zerkms    schedule 29.08.2016

Ответы (1)


arrow_upward
2
arrow_downward

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

public static void Sort(byte[] a)
{
    int[] counts = new int[256];
    for (int i = 0; i < a.Length; i++)
        counts[a[i]]++;
    int k = 0;
    for (int i = 0; i < counts.Length; i++)
        for (int j = 0; j < counts[i]; j++)
            a[k++] = (byte)i;
}
person AlexD    schedule 28.08.2016
comment
Ваш код, кажется, имеет проблему с границей. Я получаю это исключение при попытке вашей реализации: i.imgur.com/vzofi5W.png - person yq8; 29.08.2016
comment
Этот работает, спасибо. Можете ли вы объяснить, почему необходимо создание 256-элементного большого int[]? И возможны ли какие-либо другие настройки, возможно, с использованием указателей? :) - person yq8; 29.08.2016
comment
вероятно, использование указателей --- использование небезопасного кода автоматически ничего не делает лучше. Вы пытаетесь оптимизировать что-то, что вы не можете надежно измерить, это не имеет большого смысла с точки зрения оптимизации производительности. - person zerkms; 29.08.2016
comment
Сортировка подсчетом использует тот факт, что количество возможных значений в массиве ограничено (в нашем случае 256). Во время первого прохода мы просто подсчитываем, сколько у нас нулей, сколько единиц, сколько двоек и т. д. Во время второго прохода мы расставляем соответствующие числа или нули, единицы, двойки и т. д. - person AlexD; 29.08.2016