У меня есть массив структур, который содержит тип uint32_t. Зная значение max и min массива, я хочу реализовать сортировку сортировки или сортировку radix для сортировки массива на основе uint32_t. Диапазон значений может быть очень большим. Я понятия не имею, как сортировать массив структур вместо целых чисел. Или есть ли лучшие алгоритмы для такой сортировки? Благодаря!Использование сортировки сортировки/подсчета radix для массива структур в C?
Если вы используете qsort, вам необходимо предоставить функцию сравнения, как этого
struct Foo
{
uint32_t index;
other stuff;
}
int compareMyType (const void * a_, const void * b_)
{
const Foo* a = a_;
const Foo* b = b_;
if (a->index < b->index) return -1;
if (a->index == b->index) return 0;
if (a->index > b->index) return 1;
}
Foo foos[100];
qsort(foos,100,compareMyType);
десятичных сортировки могут быть быстрее, для целых чисел, но если вы действительно обеспокоены эффективностью, вы бы не сортировать массив структур, но массив указателей на структуры, поскольку на копирование данных будут существенные накладные расходы.
Спасибо за ваш ответ! Я реализовал qsort с функцией сравнения. Но как реализовать сортировку radix для сортировки массива указателей? – niu
В сортировке radix вы создаете N бункеров и перебираете массив и помещаете каждый элемент в один из бункеров (на основе цифры, которую вы сортируете), а затем объедините корзины вместе. Повторите это для каждой цифры до завершения. В вашем случае вместо того, чтобы положить * целое число * в корзину, вы помещаете * указатель * в корзину. –
Сделайте подсчетный радиус одним байтом 32-битного целого числа за раз (обратите внимание, что это должно быть сделано младшим значащим байтом, первым, самым значительным байтом последнего). Для сортировки массива потребуется 4 прохода. Вам понадобится второй массив для перемещения в/из для каждого прохода сортировки radix.
Вы сэкономите немного времени, используя 4 (каждое 32-битное целое число имеет 4 байта). X 256 (каждый байт имеет 256 возможных значений) матрица индексов (изначально это подсчеты, но конвертированные в индексы) заполняя матрицу всего одним проходом массива.
Таким образом, это всего 5 проходов чтения и 4 записи проходов массива структур с использованием сортировки count/radix на основе 4 байтов 32-битных целых значений.
Во-первых: реализовать более простой вид, такой как сортировка пузырьков, используя структуры, содержащие int. Как только вы выясните, как это сделать, вы можете перейти к сортировке radix. Не пытайтесь делать все за один шаг. – JS1
Если в ваших структурах содержатся элементы, отличные от 'uint32_t', которые вы хотите использовать в качестве ключа сортировки, тогда стандартная функция подсчета не может быть и речи, поскольку она основана на неразличимости целых чисел, имеющих одинаковое значение. Если диапазон значений большой, как вы говорите, то, вероятно, Counting Sort - это плохая идея, потому что она масштабируется как O (R + N) во времени и в памяти, где R - * диапазон * сортируемых значений. –