本文共 760 字，大约阅读时间需要 2 分钟。

归并排序和快排都用到了递归调用，但是因为递归函数所处的位置不一样，所以，导致需要的空间复杂度不一样。

其实递归调用占用的空间就是因为一个函数还没有进行完，那么去执行下一个递归的函数，那么上一个还没有进行完的函数一定要在栈中保存一定的空间，方便下一个函数调用结束时，继续执行本次函数。

而对于归并排序，它需要占空间的递归调用函数是mergesort函数

merge()

{

merge()

merge()

mergesort()（花费了o（n）个空间的就是这个函数）

merge从开始执行到现在也就是到mergesort函数开辟出一块空间

每次执行完这个mergesort函数，才会执行下一个merge函数，也就是当这个栈空间释放之后，才去执行下一个merge中的mergesort函数，这样每一个时刻需要o(n)个空间即可。并且这个不会像快排那样改变，这个不会发生变化的。

}

但是这个函数在最后的位置，所以每次在执行它的时候，只是占用了这个函数所需要的空间，也就是开辟出来的空间O(n)

而对于快速排序，

quick (a,left,right)

{

中间会开辟出一个空间

quick(a,left,i-1)

quick(a,i+1,right)

}

对于quick函数执行到quick(a,left,i-1)

因为整个函数还没有运行完，所以对应的栈空间不会释放，但是这时又要去为quick(a,left,i-1)开辟出一块新的空间

而同理，quick(a,left,i-1)有可能为它的下一个递归调用函数开辟出一块新的空间，而每次的新的空间只需要一个temp存放基准元素即可。一共发生(logn(较好和一般情况下))，所以需要的空间是O(logn)，最坏的空间复杂度是（o(n)此时发生了n次调用，退化成冒泡排序）,

转载地址：http://bwbab.baihongyu.com/