c - 通过自定义比较进行高效排序，但没有回调函数

Question

我需要一种没有回调的高效排序，但与使用 qsort() 一样可自定义。我想要的是让它像迭代器一样工作，在循环中不断调用排序 API 直到完成，在循环中进行比较而不是在回调函数中关闭。这样，自定义比较对于调用函数来说是本地的(因此可以访问本地变量，可能更有效，等等)。我已经为低效的选择排序实现了这个，但需要它是高效的，所以更喜欢快速排序导数。

有没有人做过这样的事情？我尝试这样做是为了快速排序，但试图将算法从里到外对我的大脑造成太大伤害。

下面是它在使用中的样子。

// the array of data we are sorting
MyData array[5000], *firstP, *secondP;

// (assume data is filled in)

Sorter sorter;

// initialize sorter
int result = sortInit (&sorter, array, 5000,
        (void **)&firstP, (void **)&secondP, sizeof(MyData));

// loop until complete
while (sortIteration (&sorter, result) == 0) {
    // here's where we do the custom comparison...here we
    // just sort by member "value" but we could do anything
    result = firstP->value - secondP->value;
    }

Answer 1

按照您的建议将排序功能从里到外翻转不太可能使其更快。您正在用比较函数的间接性换取项目指针的间接性。

您似乎希望比较函数能够访问状态信息。创建全局变量或全局结构的快捷方式，假设您没有同时运行多个线程。 qsort 函数直到所有数据都排序后才会返回，因此在单线程环境中这应该是安全的。

我唯一建议的另一件事是找到 qsort 的源并修改它以获取一个额外的参数，一个指向您的状态结构的指针。然后您可以将此指针传递给您的比较函数。