我有一个包含uint32_t类型的结构数组 . 知道数组的最大值和最小值后,我想实现计数排序或基数排序,以便根据uint32_t对数组进行排序 . 值的范围可能非常大 . 我不知道如何排序结构数组而不是整数 . 或者有更好的算法进行这种排序?谢谢!
如果使用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 );
对于整数,基数排序可能更快,但如果您真的关心效率,则不会对结构数组进行排序,而是排序结构指针数组,因为复制数据会产生大量开销 .
计数基数一次对32位整数的一个字节进行排序(请注意,必须首先执行最低有效字节,最后有效最高字节) . 它将需要排序4遍来对数组进行排序 . 对于基数排序的每次传递,您需要第二个数组来移动/移出 .
通过使用4(每个32位整数有4个字节)x 256(每个字节有256个可能值)索引矩阵(最初这些是计数,但转换为索引),您将节省一些时间,填入矩阵只有一次传递数组 .
因此,使用基于32位整数值的4个字节的计数/基数排序,总共5个读取通道和4个结构数组的写入通道 .
2 回答
如果使用qsort,则需要提供比较功能,如下所示
对于整数,基数排序可能更快,但如果您真的关心效率,则不会对结构数组进行排序,而是排序结构指针数组,因为复制数据会产生大量开销 .
计数基数一次对32位整数的一个字节进行排序(请注意,必须首先执行最低有效字节,最后有效最高字节) . 它将需要排序4遍来对数组进行排序 . 对于基数排序的每次传递,您需要第二个数组来移动/移出 .
通过使用4(每个32位整数有4个字节)x 256(每个字节有256个可能值)索引矩阵(最初这些是计数,但转换为索引),您将节省一些时间,填入矩阵只有一次传递数组 .
因此,使用基于32位整数值的4个字节的计数/基数排序,总共5个读取通道和4个结构数组的写入通道 .