论快速排序的时间复杂度

*如有错误，请及时联系更正，感谢

这篇帖子是关于“快速排序的时间复杂度在最坏情况下是O(n^2)，平均情况是O(n*log(n))"的原因

最坏情况

见下面代码

void quick_sort(int* a,int l,int r) { if(l>=r) { return ; } int left=l,right=r,key=left; while(left<right) { while(left<right&&a[right]>=a[key]) { right--; } while(left<right&&a[left]<=a[key]) { left++; } swap(a[left],a[right]); } swap(a[left],a[key]); key=left; quick_sort(a,l,key-1); quick_sort(a,key+1,r); }

当数据是单调递增时，由于右指针一直找不到比基准值小的数，所以会直接向左移动到1，
因此时间复杂度是O(n)。

又因为右指针会直接向左移动到1，所以左指针不动，这样key也不会变。

所以调用quick_sort(a,l,key-1);时，l是左边界，key-1是右边界，key-1 = l-1 < l，会直接返回。

而调用quick_sort(a,key+1,r); ，key+1是左边界，r是右边界，key+1 = l+1 < r（因为l<r）

而左边界会根据quick_sort(a,key+1,r);一直往右移动1个单位，得出时间复杂度递推式为
T(n)=T(n-1)+n（T(1)=1）算出T(n)=(n^2+n)/2，忽略常数项和低阶项，得出时间复杂度O(n^2)

平均情况

假设数据大小是2的次幂，左右指针相遇的位置是一定是正中心，因为左右指针一定会从左右边界经过所有区间。

因此时间复杂度是O(n)。得出时间复杂度递推式是T(n)=2T(n/2)+n（T(1)=1），其中2T(n/2)对应的是左右区间

反推：
T(1)=1，T(2)=2T(1)+2=2+2=4，T(4)=2T(2)+4=12，T(8)=2T(4)+8=32...

看出：
log(2)=1，log(4)=2，log(8)=3...

再看出：
T(2)=2*2，T(4)=4*3，T(8)=8*4...

得出T(n)=n*(log(n)+1)，忽略常数项，得出时间复杂度O(n*log(n))