C/C++中快速排序的时间空间复杂度分析 1.什么是快速排序 我理解的是，快速排序用的是分治法，运用的递归的算法，先挑选一个基准值，小于基准值的数放在左边，大于基准值的数放在基准值的右边，这样就泾渭分明的三块；但是这三块是有序的，基准值左边右边的内部数是无序的，所以，将基准值左右两端继续进行快速排序，直到区间长度为1，排序就完成了。 2.快速排序代码实现
下面使用vs2013实现快速排序：
输出为：
3.快速排序的时间复杂度 每种排序方式都会有最优的时间复杂度以及最差的时间复杂度，就像快速排序，你每次取出都取出整个数组中最小/最大的那个元素，那就是冒泡排序了，他的时间复杂度为T[n] = n * (n-1) = n^2 + n；也就是O( n^2 ) 那么最优情况下，时间复杂度如何计算呢
快速排序最优的情况就是每一次取到的元素都刚好平分整个数组(上方代码并不是最优情况)；此时的时间复杂度公式则为：T[n] = 2T[n/2] + f(n)；f[n] 就是第一次平分这个数组时所花的时间；T[n/2]是平分后的两边数组的时间复杂度，
下面来推算下，在最优的情况下快速排序时间复杂度的计算(用迭代法)：
T[n] = 2T[n/2] + n ----第一次递归令：n = n/2 = 2 { 2 T[n/4] + (n/2) } + n ----第二次递归 = 2^2 T[ n/ (2^2) ] + 2n 令：n = n/(2^2) = 2^2 { 2 T[n/ (2^3) ] + n/(2^2)} + 2n-----第三次递归= 2^3 T[ n/ (2^3) ] + 3n令：n = n/( 2^(m-1) ) = 2^m T[1] + mn ----第m次递归(m次后结束)
当最后平分的不能再平分时，也就是说把公式一直往下跌倒，到最后得到T[1]时，说明这个公式已经迭代完了（T[1]是常量了）。
得到：T[n/ (2^m) ] = T[1] ===>> n = 2^m ====>> m = lgn；
T[n] = 2^m T[1] + mn ；其中m = lgn;
T[n] = 2^(lgn) T[1] + nlgn = n T[1] + nlgn = n + nlgn ；其中n为元素个数
又因为当n >= 2时：nlgn >= n (也就是lgn > 1)，所以取后面的 nlgn；
综上所述：快速排序最优的情况下时间复杂度为：O( nlgn )
4.快速排序空间复杂度 快速排序的使用空间是O（1）；其主要的空间复杂都在递归上了
最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况
最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况
问一个问题：怎么才能避免变成冒泡排序提高效率呢？