首页 文章

对C中的结构数组使用基数排序/计数排序?

提问于
浏览
1

我有一个包含uint32_t类型的结构数组 . 知道数组的最大值和最小值后,我想实现计数排序或基数排序,以便根据uint32_t对数组进行排序 . 值的范围可能非常大 . 我不知道如何排序结构数组而不是整数 . 或者有更好的算法进行这种排序?谢谢!

2 回答

  • 0

    如果使用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 );
    

    对于整数,基数排序可能更快,但如果您真的关心效率,则不会对结构数组进行排序,而是排序结构指针数组,因为复制数据会产生大量开销 .

  • 0

    计数基数一次对32位整数的一个字节进行排序(请注意,必须首先执行最低有效字节,最后有效最高字节) . 它将需要排序4遍来对数组进行排序 . 对于基数排序的每次传递,您需要第二个数组来移动/移出 .

    通过使用4(每个32位整数有4个字节)x 256(每个字节有256个可能值)索引矩阵(最初这些是计数,但转换为索引),您将节省一些时间,填入矩阵只有一次传递数组 .

    因此,使用基于32位整数值的4个字节的计数/基数排序,总共5个读取通道和4个结构数组的写入通道 .

相关问题