快速排序最好的情况是每次把上一次的数组平均分成两个子数组。设数组总数一共为n，如果把这n个数每次分成2半最后每个数组只包含一个元素，假设要分k次，则2的k次方=n，解得k=log2 n（log以2为底对n取对数）.也就是说要分log2 n次，而每次都是处理n个数据。所以总的时间复杂度为O（n*log2 n）。
第一趟要遍历整个数组复杂度为n很好理解，接下来的log2n实际上和二分法查找规律差不多，每次的规模减半，设计算次数为x，则n = 2^x，所以x = log2n。
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024