关于快速排序的问题关于实现快速排序的信息，请参考这个博客。
3分钟内记住快速排序(图解说明，有代码，容易理解) ) ) ) ) ) ) ) ) ) ) )。
快排的核心函数如下：
voidquicksort(intarr[]，int low，int high ) lowhigh ) intpi=partition ) arr，low，high； 快速终止(arr，low，pi - 1 )； quicksort(ARR，pi 1，high )； }在最坏的情况下，递归如下：
快速终止(arr，1，n ) ) ) )。
快速引导(arr，1，n-1 ) ) ) ) ) ) )。
快速引导(arr，1，n-2 ) ) ) ) ) ) )。
快速引导(arr，1，n-3 ) ) ) ) ) ) )。
水平。
水平。
水平。
快速终止(arr，1，1 ) ) ) )。
使用下面的递归树，可以更好地看出树的深度是n
如上图所示，这种情况下堆栈需要o(n )、o(n )、o(n )、o(n )和o(n )空间
在while中进行尾部递归优化后的快速排序voidquicksort(intarr[]，int low，int high ) lowhigh ) intpi=partition ) arr，low，high if(pi-lowhigh-pi ) quicksort ) arr，low，pi - 1 )； low=pi 1； }else{quicksort(arr，pi 1，high )； high=pi - 1； }}在上面的代码中，如果左侧部分的长度小，则递归调用左侧部分，否则递归调用右侧部分。
此时使用o(LOGN ) o ) Logn ) o ) Logn )制造多馀的空间。
如果末尾递归函数在末尾位置调用自身，则将该情况称为尾递归。 尾部递归是在尾部直接调用自身递归函数的特殊尾部调用。
函数本身调用次数过多会导致递归层数加深，堆栈爆炸。
举个例子：
调用defrecsum(5(x ) : ifx==1: returnxelse : returnxrecsum ) x-1 ) recsum )5)时，堆栈调用如下：
recsum(5) )。
5recsum(4) )。
5 )4recsum(3) )
5(4) 3recsum )2) )
5(4)3) 2recsum(1) )
5(4)3)2) )
5(4)3) )
五(四)六)
5 10
15
可以看出递归的深度很深
可以通过以下方式优化尾部递归：
与deffoo(x，sum=0) : ifx==0: returnsumelse : return foo (x-1，sum x ) )对应的调用如下：
五零)。
foo (4，5 ) )。
foo (3，9 ) )。
foo (2，12 ) )。
foo (1，14 ) )。
foo (0，15 ) )。
15
很容易看出这是一个线性调用
函数调用堆栈用于记录在程序运行时分配了一定的内存空间，其中一部分被程序调用的每个函数的执行情况。 这就是函数的调用堆栈。
在常规函数调用中，新的堆栈帧(也称为stack frame、“堆栈帧”或简称为“帧”)始终添加到调用堆栈的顶层。 此过程称为“堆栈入”或“堆栈”，意味着将新帧推到堆栈的顶层。
如果函数具有非常多的调用级别，则调用栈会消耗大量内存，并会爆炸内存空间。