使用radix排序/计数排序用于C中的结构数组

Question

我有一个包含UINT32_T类型的结构数组。了解数组的最大值和最小值，我想实现计数排序或radix排序以基于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 );

对于整数而言，radix排序可能更快，但是如果您真的担心效率，则不会对结构排序，而是将一系列指针分类为结构，因为在复制周围的数据时会有很大的开销。

Answer 2

一次计数radix排序32位整数的一个字节（请注意，这必须是最不重要的字节，首先是最重要的，最重要的字节）。它将进行4个通过以排序数组。对于radix排序的每个通过，您需要第二个数组才能移动/从。

您可以通过使用4（每个32位整数具有4个字节）x 256（每个字节具有256个可能的值）矩阵（最初是计数，但转换为索引），填充

x 256（每个字节具有256个可能的值），填充，

您可以节省一些时间。在矩阵中，只有一个数组的一个通过。

因此，基于32位整数值的4个字节的计数/radix排序，总共5次读取和4个结构数组的写入。