（快速排序的栈深度）对于QUICKSORT算法包含了两个对其自身的递归调用。在调用PARTITION后，QUICKSORT分别递归调用了左边的子数组和右边的子数组。QUICKSORT中的第二个递归并不是必须的。我们可以用一个循环控制结构来代替它。这一技术成为尾递归，好的编译器都提供这一功能。考虑下面这个版本的快速排序，它模拟了尾递归情况：
TAIL-RECURSIVE-QUICKSORT(A,p,r) 1 while p<r 2 //Partition and sort left subarray 3 q=PARTITION(A,p,r) 4 TAIL-RECURSIVE-QUICKSORT(A,p,q-1) 5 p=q+1
a.证明：TAIL-RECURSIVE-QUICKSORT(A,1,A.length)能正确的对数组A进行排序。编译器通常使用栈来存储递归执行过程中的相关信息，包括每一次递归调用的参数等。最新调用的信息存在栈的顶部，而第一次调用的信息存在栈的底部。当一个过程被调用时，其相关信息被压入栈中；当它结束时，其信息则被弹出。因为我们假设数组参数是用指针来指示的，所以每次过程调用只需要O(1)的栈空间。栈深度是在一次计算中会用到的栈空间的最大值。
b.请描述一种场景，使得针对一个包含n个元素数组的TAIL-RECURSIVE-QUICKSORT的栈深度是)
。
c.修改TAIL-RECURSIVE-QUICKSORT的代码，使其最坏情况下栈深度是)
，并且能够保持O(nlgn)的期望时间复杂度。
