快速排序时间复杂度分析：

数组长度为n

1，平均复杂度：

t(n) = cn + 2t(n/2)

= cn + 2(cn/2 + 2t(n/4)) = 2cn + 4t(n/4)

= 2cn + 4(cn/4 + 2t(n/8)) = 3cn + 8t(n/8)

= icn + 2^i * t(n/(2^i))

当 2^i = n时, i = logn, 排序结束，

t(n) = cnlogn + n*t(1) = o(nlogn)

2，最坏复杂度：

在完全有序的情况下[比如从小到大有序]

i从开始，j从末尾向中间移动，选第一个元素a[0]为key，

i找第一个比key大的元素，a[1]符合条件，停止移动。

j找第一个比key小的元素，直到a[1]都没找到，停止移动

判断 key < a[1]不交换，

数组被划分为两部分 a[0]和 a[1]~a[n]

如此，以后每次划分都只能划掉一个元素，由此，时间复杂度推导如下：

t(n) = cn + t(n-1) = cn + c(n-1) + t(n-2) ....

= cnn -ck + t(1) = cn^2 = 0(n^2)

冒泡排序的时间复杂度分析：

第一个元素：cn

第i个元素: cn

第n个元素: cn

总：n*cn = o(n^2)

参考文章如下：