algorithm - 关于快速排序 killer

Question

你们中的一些人可能偶然发现了这篇可爱的文章 - http://igoro.com/archive/quicksort-killer/\

真正有趣的是他如何修复快速排序以在 O(N log N) 内针对定义的对手执行。

the quicksort might choose the median element as the pivot at each step, thus always geting a perfect split of the input sequence into two halves. Median can be found deterministically in O(N) running time, and so the total running time is always O(N log N).

我的问题是线性时间中值查找算法最终不会使用相同的比较函数并在 O(N^2) 而不是 O(N) 中执行吗？

编辑:

准确地说:我质疑基于分区的中值选择算法的复杂性，该算法使用类似于快速排序的策略，并且将使用与快速排序相同的比较函数。它如何在 O(N) 中与这个对手一起工作？

Answer 1

won't the linear time median-finding algorithm end up using the same compare function and perform in O(N^2) instead of O(N)?

不，通过添加一个 O(N) 函数来找到中位数，复杂度变为

O((N+N) log N) == O(2N log N) == O(N log N)

但是，正如该文章所述，增加的常量使它没有吸引力。

标准技术称为 median-of-3，完整的中值搜索不会真正改善它。

如果最坏的情况很重要，那就不要使用快速排序。 Shellsort 有更好的上限。