QuickSort寻找中位数？

Question

为什么使用QuickSort查找一组数字的中位数时，为什么最坏的方案$ mathcal {o} left（n^2 right）$？

• 如果您的算法不断选择大于或小于 全部 列表中的数字不会失败？例如，数字列表是：

  $ s =（12,75,82,34,55,15,51）$

  而且，您不断选择大于$ 82 $或低于$ 12 $的$ 12 $的数字，您的套装不会始终保持相同的尺寸吗？

• 如果您的算法不断选择一个创建$ 1 $的标准的数字，为什么最坏的情况是$ MATHCAL {O} left（n^2 right）$？考虑到根据 师父定理, ，$ d> log_b a $？

*其中$ d $是效率指数（即线性，指数等），$ b $是每次迭代时问题大小的因素，$ a $是子问题的数量，$ k $是级别。全比：$ t（n）= Mathcal {o} left（n^d right） *（ frac {a} {b^d}）^k $

Answer 1

QuickSort用于排序，您所指的算法是一种选择算法 快速选择.

• 由于您只能选择枢轴列表中的数字＃1从未发生过。
• 最坏的情况是，您不断选择一个将列表分为2个列表的数字：只有一个元素的列表和一个带有$ n-1 $元素的列表，如果在每次迭代中是这种情况，您只排除单个元素。

因此，您要进行$ n $操作，第二次迭代$ n-1 $操作，第三个$ n-2 $操作，...最后一个迭代1操作。

它是第一个$ n $自然数的总和：

$ 1+2+3+...+（n-2）+（n-1）+n = n = n（n-1）/2 $ operations = $ o（n^2）$