快速排序

[hunterhug]

https://hunterhug.github.io/goa.c/#/algorithm/sort/quick_sort

Description

[hunterhug]

快速排序用得比较多，有必要学习

[baici1]

问一个问题：
快排的计算公式T(n) = 2*T(n/2) + O(n)

下面的具体计算的时候是 T(n) = 2*T(n/2) + n/2

为什么是 O(n)=n/2?

[hunterhug]

问一个问题： 快排的计算公式T(n) = 2*T(n/2) + O(n)

下面的具体计算的时候是 T(n) = 2*T(n/2) + n/2

为什么是 O(n)=n/2?

你可以接着往下看，最好情况和最差情况。分析最好情况时认为 O(n)=n/2。

[baici1]

你可以接着往下看，最好情况和最差情况。分析最好情况时认为 O(n)=n/2。

在这里我想跟你 battle 一波。
我觉得你的 n/2 是有问题的。
举例：在这一组数组中[4,1,3,2,6,5,7]，对于第一次的遍历 4 就会放在中间，就是最好的情况！
但是其实在partition,会比较 5 次。还差一次的比较就是后面array[i] >= array[begin]
说到底你还是比较了 6 次，也就是 n 次。

快排的时间性能不是取决于单次的比较，而是递归的深度。
最好的情况是每次都平均分割，他的深度就是 log2(n)
下面这张图我觉都是比较正确的！

[hunterhug]

你可以接着往下看，最好情况和最差情况。分析最好情况时认为 O(n)=n/2。

在这里我想跟你 battle 一波。 我觉得你的 n/2 是有问题的。 举例：在这一组数组中[4,1,3,2,6,5,7]，对于第一次的遍历 4 就会放在中间，就是最好的情况！ 但是其实在partition,会比较 5 次。还差一次的比较就是后面array[i] >= array[begin] 说到底你还是比较了 6 次，也就是 n 次。

快排的时间性能不是取决于单次的比较，而是递归的深度。 最好的情况是每次都平均分割，他的深度就是 log2(n) 下面这张图我觉都是比较正确的！

按照常规的想法，快速排序就是一个基准数，然后全部数和它比较，大的在这个数左边，小的在这个数右边，这样可以认为比较规模为N次了。

我们的算法是从两边同时向中间夹逼，其实算起来确实比较规模是N次。

你发现了一个问题，要把 n/2 变成 n。