快速排序最好最坏情况
墨初 知识笔记 176阅读
快速排序复杂度最坏情况是什么？
答：快速排序复杂度最坏情况 (O (n^2))证明： 最坏情况 下就是对已经排好序的序列操作，假设是从小到大，那么last就会从 最 后一直比到first (哨兵位置) (共比较n-1次)，并且将序列分为1 和 n-1，之后n-1以类似方式被递归划分。 假设算法每次都进行了这种不对称划分，划分的 时间 代价为θ (n) [//n...
快速排序的时间性能取决于什么？
答：快速排序 的时间性能取决于 快速排序 递归的深度，可以用递归树来描述递归 算法 的执行情况。 如图9‐9‐7所示，它是 {50,10,90,30, 70,40,80,60,20}在 快速排序 过程中的递归过程。 由于我们的第一个关键字是50，正
为什么快速排序比其他排序算法更有优势？
答：因为基准值是相当均匀地落在排列好的数列次序之任何地方，总和就是所有可能分割的平均。 这个意思是，平均上快速排序比理想的比较次数，也就是最好情况下，只大约比较糟39%。 这意味着，它比最坏情况较接近最好情况。 这个快速的平均运行时间，是快速排序比其他排序算法有实际的优势之另一个原因。 空间的消耗主要是递归造成的栈空间使用，最好情况，递归树的深度为log2n，其空间复杂度也就为O (logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O (n)，平均情况，空间复杂度也为O (logn)。
快速排序算法的时间复杂度是多少？
答：然后，获得的枢轴将数组一分为二，那么各自还需要T（n/2）的时间（注意是最好情况，所以平分两半）。 于是不断地划分下去，我们就有了下面的不等式推断。 …… 也就是说，在最优的情况下，快速排序算法的时间复杂度为O (nlogn)。 在最坏的情况下，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。