如果中位数算法的中位数不会改变快速排序的平均情况复杂度，为什么要使用它？
If the median of medians algorithm doesn't change the avg-case complexity of quicksort, why use it?
考虑到排序算法的平均情况复杂度 Omega(n*lg(n)) 的硬下限，when/why 你会决定花时间用快速排序来实现这个选择算法，而不是仅仅使用一个随机主元还是数组中的第 (n/2) 个简单位置？
因为它有一个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.
考虑到排序算法的平均情况复杂度 Omega(n*lg(n)) 的硬下限，when/why 你会决定花时间用快速排序来实现这个选择算法，而不是仅仅使用一个随机主元还是数组中的第 (n/2) 个简单位置？
因为它有一个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.