为什么快速排序是N日志■直观的解释吗？(Intuitive explanation for why

是任何人能给出一个“简单的英语直观的，但正式的，是什么使快速排序的n log n说明？ 从我的理解它使一个传过n个元素，而它这样做日志N次...林不知道如何把它变成文字，为什么它这样做日志n次。

Answer 1:

每个分区操作花费O（N）的操作（一次通过在阵列上）。 在平均每个分区划分阵列以两个部分（其总结了登录n个操作）。 我们共为O（n * log n）的操作。

即，在平均log N分割的操作，并且每个分区需要O（n）的操作。

Answer 2:

该log n一部分来自突破一半的输入在每次迭代的事实，这是（至少理想情况下）。 从N个项目开始，并打破那些半每次意味着你到后日志_2（N）次迭代1项，此时你显然不能进一步细分它的任何。 例如，从，比如说，128项开始，则分成64组，32，16，8,4，2，1项- 7次迭代（和日志_2（128）= 7）。

每个那些迭代扫描通过整个阵列进行分区，所以每一个都具有O（N）的复杂性。

在这两者之间，你结束了O（日志N）的操作，其中的每一个具有为O（n）的复杂性，为O（n log n）的整体复杂性。

技术上正确，快速排序的大澳实际上是O（N ^2）虽然。 出现这种情况的事实，分隔元件的足够不好的选择可以在阵列分割成一个元件在一侧，而在另一阵列的整个其余部分。 如果这种情况发生在每次迭代，需要N次迭代它每人被拆下来到一个元素的作品，所以你得到个运算，每一个复杂度O（N），为O（N * N）的整体。

在实际的实现，你通常在这之前停止，但是这是你可以去最远。

Answer 3:

嗯，这并不总是N（log n）的。 这是当选择的枢轴大致在中间的性能时间。 在最坏的情况下，如果你选择最小的或最大的元素为支点，则时间会为O（n ^ 2）。

为了形象化“N日志N”，你可以假设枢轴最接近的是元素的平均阵列中的所有元素进行排序。 这将所述阵列划分成2份大致相同的长度。 在这两种应用的快速排序程序。

如你去减半阵列的长度的每个步骤，直到抵达长度= 1即1个元件的排序后的数组，你会做这个日志N（基数为2）倍。

Answer 4:

在-事实上你需要找到所有的N个元素（枢转）的位置，但比较的最大数目是对于logN个每个元素（第一个是N，第二枢转N / 2,3rd N / 4..assuming枢轴是中位数元素）

文章来源: Intuitive explanation for why QuickSort is n log n?