c - 在 C 中对结构数组使用基数排序/计数排序？

Question

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

Answer 1

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

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