快速排序法:空间复杂度O(1),原地和栈使用空间的定义是否有矛盾？
来源：3-1 基于比较排序算法大总结
慕田峪2135618
2024-03-20 16:57:15
老师，今天回过头来看排序算法，快速排序的实现无法绕过栈的使用(即使不使用递归而是显式维护一个栈模拟递归过程)，栈使用的空间复杂度与深度相关，平均情况O(logn),最坏情况O(logn)。递归/显式栈的空间使用应该是算法空间开销的一部分。那么，快速排序“空间复杂度O(1)”,“是一个原地排序算法”的提法，是不是存在矛盾？讨论时是否不应该忽略栈的空间开销？
写回答
1回答
-
你的理解是非常正确的。快排的空间度应该是 O(logn)，logn 是递归调用栈的深度。
这和“原地排序”不冲突。实际上原地排序并不是一个被非常严谨定义地概念。原地排序就是指，我们不需要开辟一个完整的 O(n) 的空间，把原来的数组中的元素复制一遍，才能排好序。只利用最初给定的数组，就能完成这个排序。从这个意义上，快排是原地排序。
值得一提的是，如果快排不需要“原地排序”这个限制的话，将非常容易完成。对于每次 partition 的过程，都开一个一样大小的辅助空间 temp。小于 Pivot 的元素从前往后放进 temp，大于 pivot 的元素从后往前放进 temp，别忘了最后放 temp，然后把 temp 再拷贝回原始数组 num 中相应位置就好了。
继续加油！：）
0
相似问题