我有一个大小为 n 的数组等待排序。但与普通的排序问题不同，我必须使用特定的比较器，它接收三个数字并告诉这三个数字的最大值和最小值。我的目标是在对数组进行完全排序之前尽可能少地使用比较器。我可以使用什么策略？
感谢您的帮助!
最佳答案
由于您的三向比较器可以通过对普通比较器的三次调用来实现，这意味着我们无法将任何普通排序算法改进超过 3 倍。更仔细的论证表明，因为每三个方式比较为我们提供了 log2 6 ≈ 2.585 位信息，我们无法提高更多的信息。直观上，当使用普通比较器排序时，您可能会比较 a <= b和b <= c ，因此不需要比较 a和c反正;因此可能的加速因子可以小至 2。
因此，渐近地，我们仍在寻找 O(n log n) 算法，问题是如何利用比较器来进行更少的比较至少一个因子 2。首先要尝试的“明显”事情是修改现有的基于比较的排序算法；一个好的候选人是自下而上的 heapsort ，在平均情况下进行大约 n log 2 n 次比较，在最坏情况下进行 1.5 n log 2 n 比较(Wikipedia)。这击败了标准快速排序算法，后者在平均情况下执行大约 1.39 n log2 n 次比较 ( Wikipedia )。
该算法使用堆上的两个基本操作“向下筛选”和“向上筛选”。
- “向下筛选”操作需要将父元素与其两个子元素进行比较，以查看父元素是否大于或等于其两个子元素，如果不大于或等于，则应将父元素与哪个子元素交换。我们可以使用三向比较器同时比较父级与两个子级。
- “向上筛选”操作将子级与其父级进行比较，如果顺序不正确则交换它们；然后一直重复此操作直至根节点。我们可以使用三向比较器将子节点与其父节点和祖父节点进行一次比较。
堆排序算法仅在这两个操作中调用比较器，并且对于这两个操作，三路比较器的调用次数可以减少 2 倍。这不一定是您能做的最好的事情，但它从一个非常高效的算法，并且符合直觉给出的最坏情况加速因子。
关于c++ - 使用三数比较器排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/59356416/