使用自定义交换的 C++ 排序实现？

Question

关于如何在 C++ 中一次对多个数组进行排序，有很多问题被问到。答案总是相同的，即使用结构 vector 而不是多个数组。不幸的是，由于多种原因(I/O、部分 MPI 传输、矢量化单元的利用等)，我不能这样做。此外，由于内存限制，我无法在排序后将结构数组转换为独立数组。我的问题是，是否存在任何可以与自定义交换(和自定义比较)操作一起使用的高效 (n log n) 排序算法的 C++ 实现？

(我仍然不明白为什么STL中缺少这样一个选项。显然，很多C++程序员都在要求它。)

Answer 1

您可以不完全对数据进行排序，而只能对其他数组和自定义比较器的索引进行排序。排序后，您将拥有排序索引数组，对于 O(n) 您可以置换所有数组。