quicksort可以与多个阵列一起使用吗？

Question

我在C中有一个高性能,无等待的向量实现,允许我线性索引数组,但是使用多个数组实现.现在我需要对这个向量进行排序.显然我不能使用qsort()标准函数,因为数组不是单个内存块.

虽然没有这样实现,但假设60个槽位向量被定义为:

struct vector {
  int *buckets[4];
};

struct vector v;
v.buckets[0] = calloc(4, sizeof (int));
v.buckets[1] = calloc(8, sizeof (int));
v.buckets[2] = calloc(16, sizeof (int));
v.buckets[3] = calloc(32, sizeof (int));

我有一个简单的内联函数,可以将给定的索引值调整为0到59(例如,getval(8)将返回buckets[1][4]并getval(9)返回buckets[1][5]等).

因此,虽然矢量可以线性索引,但它不是线性存储的.可以使用quicksort来对这个向量进行排序吗？如果没有,我应该看看任何其他排序算法？

Answer 1

只要你有相同的getval(index)和setval(index, value),几乎任何排序算法(包括quicksort)都可以.

但是,您无法使用qsort标准库,因为这需要连续的数据.因此,您必须编写自己的排序函数或引入间接级别,例如,通过创建索引数组,使用它进行排序qsort,然后将索引的结果重新排序应用于底层数组存储.