高效的排序方式，使用自定义比较，但没有回调函数。

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;
    }

- rob

---

如果你要这样做，最好也将交换操作从排序函数中分离出来。不过这是一个有趣的想法，我喜欢把算法翻转过来。 - nategoose

你不能这样做。C语言没有lambda函数，所以你需要回调函数。或者：你可以硬编码排序器，针对特定类型的数据和比较函数进行排序。 - wildplasser

Answer 1

将排序函数像您提出的那样翻转不太可能使其更快。您正在将比较函数上的间接引用与项目指针上的间接引用进行交换。

看起来您想让比较函数访问状态信息。一种快速且简单的方法是创建全局变量或全局结构，假设您一次只有一个线程在运行。 qsort函数将在所有数据排序完毕后才返回，因此在单线程环境中，这应该是安全的。

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

- Mark Ransom

---

我并不是真的想让它更快（虽然我希望通过使其更容易内联来实现这一点），我只是不想让它比我的选择排序实现慢很多。我确实需要支持线程环境。我可以像你建议的那样，在qsort中添加状态指针...这会有很大帮助，但最终我希望采用“迭代器风格”，因为我更喜欢那种API。我已经使用我的实现（使用选择排序）几年了（当性能不是一个重要因素时），它可以使事情变得如此干净和易于使用。 - rob

Answer 2

一种简单的解决方案是使用内联排序函数和内联比较回调。当编译时进行优化时，两者都会被精简成你想要的样子。唯一的缺点是你的排序算法选择受到限制，因为如果你递归或分配更多内存，你可能会失去任何从中获得的好处。像这样开销小的方法，最适合小数据集。

您可以使用具有比较方法、大小、偏移和步幅的通用排序函数。这样，自定义比较可以通过参数而不是回调来完成。使用这种方式，您可以使用任何算法。只需使用一些宏填充最常见的情况，因为您将有很多函数参数。

此外，请查看STB库（https://github.com/nothings/stb）。它有类似于这个的排序函数，以及许多其他有用的C工具。

- Philip J. Fry

Answer 3

将现有的qsort实现更新为引用Sorter对象作为其本地变量。它不再调用传递进来的比较函数，而是更新其状态并返回给调用者。

由于qsort中存在递归，您需要在Sorter对象中保留某种状态堆栈。您可以使用数组或链表进行动态分配（效率较低）来完成这项工作。由于大半部分使用尾递归，并对枢轴点的较小一半进行递归调用qsort，因此如果您的数组可以容纳n个状态，则可以排序至少2ⁿ个元素。

- tomlogic

---

是的，我认为这正是我想做的，但是“返回给调用者”而不是调用比较函数实际上将整个过程颠倒了过来，虽然我知道它可以完成，但是非常困难...所以我希望有人已经在某个地方完成了它。 :) - rob

Answer 4

你可以编写一个预处理器宏来输出排序程序，并让宏将比较表达式作为参数。

#define GENERATE_SORT(name, type, comparison_expression) \
  void name(type* begin, type* end) \
  { /* ... when needed, fill a and b and use comparison_expression */ }

GENERATE_SORT(sort_ints, (*a<*b))

void foo()
{
    int array[10];
    sort_ints(array, array+10);
}

- Matt Curtis

---

以下是将此方法应用于数据结构的示例 --> http://attractivechaos.wordpress.com/2008/09/02/generic-programming-in-c/ <-- 这不是为胆小者准备的，个人而言，我讨厌调试那种代码，但如果您已经优化了其他所有内容并真正想要挤出函数调用的开销，您可以在纯C中实现它。 - Matt Curtis

哎呀，我见过一个宏定义的qsort，它非常可怕。然而，我的请求意图更多地与不需要全局变量的易于使用的API有关，而不是纯粹的速度。我只是觉得使用回调函数比直接在那里完成工作更麻烦。 - rob

也许我们可以向C标准委员会请愿添加lambda表达式！这将为宏、尾递归、垃圾收集和更多的括号打开大门;-) - Matt Curtis

Answer 5

你所要求的已经被实现了——它被称为std::sort，并且已经包含在C++标准库中。更好的支持（以及许多其他功能）是良好编写的C++通常比C更快的原因之一。

- Jerry Coffin

---

当问题的标签为“C”时，指出C++的sort函数更好并不是非常有用。 - Mark Ransom

我对std::sort的理解是，除非您正在对其支持的标准类型之一进行排序，否则它需要一个比较函数。正如Mark所指出的那样，我需要它用于C语言，但如果std::sort实际上按照我想要的方式执行，我可以借用一个实现并将其转换为在C中运行。然而，情况似乎并非如此。 - rob

重点是，在C语言中没有一个好的方法来处理这个问题——但他的C代码可能容易转换为C++，因为在C++中存在好的解决方案。是的，在C++中有一个比较函数（或函数对象），但由于std::sort是一个模板，所以比较通常会生成内联代码。理论上你可以用一些C宏来做同样的事情，但我怀疑这是可行的。简而言之，通过转换为C++是最实际的解决方案（远胜其他方式）。 - Jerry Coffin

@Jerry：你真的可以推荐转换到C++，而不知道更多关于程序的信息，比如平台和代码行数吗？对于超过100,000行的程序，转换为C++将比尝试适应std::sort的技术到vanilla C要更费力。我们所知道的是，rob（OP）可能在嵌入式平台上，并且没有可用的C++编译器。 - tomlogic

@Matt：我以前看过这篇抨击文章。你能在那里找到的唯一有说服力（或任何其他类型的）理由纯粹是政治原因：如果你想编写Linux内核代码，C++显然会被直接拒绝，所以使用C是一个理由。从技术角度来看，他似乎只是表现出了故意无知。 - Jerry Coffin

Answer 6

两点。一）。

   _asm    

II). 编译器的基本设计限制。
编译器作为基本目的，其设计目标是避免使用汇编或机器代码。它们通过强加一定的限制来实现这一点。在这种情况下，我们放弃了在汇编代码中可以轻松完成的灵活性。即将生成的排序代码在调用比较函数时分成两个部分。将第一部分的代码复制到某个位置。接下来将比较函数的生成代码复制到第一部分之前刚刚复制的代码后面。然后复制排序代码的最后一半。最后，我们还必须处理整个系列的细节问题。另请参阅"热修补"运行程序的概念。

- sys101