快速排序 空间
终极管理员 知识笔记 94阅读
什么是快速排序？
答：最终其时间复杂度为O (n^2)。 空间复杂度也为O (logn)。 快速排序是一种不稳定的排序方法。 文本与公式书写使用typora，但是typora不支持公式左对齐，所以写出来比较难看。
快速排序的空间复杂度是多少？
答：快速排序只是使用数组原本的空间进行排序，所以所占用的空间应该是常量级的，但是由于每次划分之后是递归调用，所以递归调用在运行的过程中会消耗一定的空间，在一般情况下的 空间复杂度 为 O (logn) ，在最差的情况下，若每次只完成了一个元素，那么空间复杂度为 O (n) 。 所以我们一般认为快速排序的空间复杂度为 O (logn) 。
快速排序时间复杂度和冒泡排序一样吗？
答：但是快速排序在最坏情况下的 时间复杂度 和冒泡排序一样，是 O (n 2) ，实际上每次比较都需要交换，但是这种情况并不常见。 我们可以思考一下如果每次比较都需要交换，那么数列的平均时间复杂度是 O (nlogn) ，事实上在大多数时候，排序的速度要快于这个平均时间复杂度。
快速排序的时间性能取决于什么？
答：快速排序 的时间性能取决于 快速排序 递归的深度，可以用递归树来描述递归算法的执行情况。 如图9‐9‐7所示，它是 {50,10,90,30, 70,40,80,60,20}在 快速排序 过程中的递归过程。 由于我们的第一个关键字是50，正 排序算法之 快速排序 及其时间复杂度和空间复杂度 _not... 最坏情况是枢纽元为最大或者最小数字,那么所有数都划分到一个序列去了 时间复杂度 为O (n^2) 快速排序 是排序算法中效率相对较高的,但使用的人却是比较少,大家一般信手拈来的排序算法就是冒泡排序。 因为冒泡排序主观,容易理解,而快速... 快速排序 的 时间复杂度 分析_车子 (chezi)_请分析随机快速...