algorithm - 如果中位数算法的中位数不会改变快速排序的平均情况复杂度，为什么要使用它？

Question

鉴于排序算法的平均情况复杂度 Omega(n*lg(n)) 的硬下限，您何时/为什么决定花时间使用快速排序而不是仅使用随机主元或仅数组中第 (n/2) 个简单位置？

Answer 1

因为它有一个 better worst-case time complexity .

The approximate median-selection algorithm can also be used as a pivot strategy in quicksort, yielding an optimal algorithm, with worst-case complexity O(n log n). Although this approach optimizes quite well, it is typically outperformed in practice by instead choosing random pivots, which has average linear time for selection and average log-linear time for sorting, and avoids the overhead of computing the pivot. Median of medians is used in the hybrid introselect algorithm as a fallback, to ensure worst-case linear performance: introselect starts with quickselect, to obtain good average performance, and then falls back to median of medians if progress is too slow.