为什么QuickSort是n log n的直观解释？
是否有人能够给出“简单英语”的直观而正式的解释让QuickSort记录n的原因？ 根据我的理解，它必须对n项进行传递，并且它会记录n次......我不确定如何将它记录到文字中，以便它记录n次。
每个分区操作都需要O（n）个操作（数组上的一个操作）。 平均而言，每个分区将数组分成两部分（总计记录n个操作）。 总的来说，我们有O（n * log n）操作。
即在平均log n分区操作中，每个分区执行O（n）个操作。
log n部分来自这样一个事实，即每次迭代时（至少理想情况下）将输入分为两半。 从N个项目开始，每次将这些项目分成两半意味着在log2（N）迭代之后您下降到1个项目，此时您显然不能再细分它。 例如，从128个项目开始，您将分成64,32,16,8,4,2,1个项目组--7次迭代（和log2（128）= 7）。
每个迭代扫描整个数组以对其进行分区，因此O（logN）操作结束，每个操作都具有O（n）复杂度，对于O（n log n）总体复杂性。
为了在技术上正确，Big-O是O（N2）。 这是由于一个足够差的分区元素选择可能会将阵列分割成一个元素而另一个元素的整个其余部分。 如果每次迭代都发生这种情况，则需要N次迭代才能将其分解为每个元素的片段，因此您可以获得N个操作，每个操作的复杂度为O（N），总体上为O（N * N）。
在实际执行过程中，您通常会在此之前停止，但这是您可以走得最远的地方。
那么，它并不总是n（log n）。 这是选择枢轴大致在中间的表演时间。 在最坏的情况下，如果你选择最小或最大的元素作为支点，那么时间将是O（n ^ 2）。
为了可视化'n log n'，可以假定pivot是最接近要排序的数组中所有元素的平均值的元素。 这会将阵列分成大致相同长度的2个部分。 在这两者上，你都应用了快速排序程序。
就像在每一步中你将数组的长度减半一样，你将这样做log n（base 2）次，直到达到length = 1即1个元素的排序数组。
链接地址: http://www.djcxy.com/p/39683.html