快速排序，冒泡排序时间复杂度推导

快速排序时间复杂度分析：数组长度为n1，平均复杂度：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)

参考文章如下：

https://www.cnblogs.com/surgewong/p/3381438.html