|
在《大话数据结构》中，看到快速排序的尾递归优化，不太清楚它的尾递归怎么比传统快排更优。查找了一些资料，现在记录一下自己的理解吧。
传统快排：
void quickSort(SqList * list , int low ,int high)
{
int pivot;
while(low<high)
{
pivot=Partition(list,low,high);
quickSort(list, low,pivot - 1);
quickSort(list,pivot+1,high);
}
}
《大话数据结构》里尾递归优化后的：
void quickSort(SqList * list , int low ,int high)
{
int pivot;
while(low<high) //改成循环
{
pivot=Partition(list,low,high);
quickSort(list, low,pivot - 1);
low = pivot+1; /*尾递归*/
}
}
我认为单单这样，是不能起到优化作用的。自己模拟走一遍，这样优化后的快排的过程跟传统都是一样的，都是先对枢轴左边的子数组递归调用，再对枢轴右边的子数组递归调用，只不过对枢轴右边的子数组的递归调用放到了下一次循环里。倘若是极端的例子，即划分极度不均衡，每次枢轴点右面的子数组大小都仅为一个，递归树都将是一颗斜树，优化后的和传统的递归深度也都趋近于n，没有什么优化。
不过幸运的是，我在找资料时发现，倘若将尾递归优化+两者取短结合起来，倒是可以将最坏情况下空间复杂度压缩至logn，如下代码。
void quickSort(SqList * list , int low ,int high)
{
int pivot;
while(low<high) //改成循环
{
pivot=Partition(list,low,high);
if ((pivot-low)<(high-pivot)) //两者取短 + 尾递归优化，最坏空间复杂度优化至logn
{
quickSort(list, low,pivot - 1);
low = pivot+1; /*尾递归*/
}
else
{
quickSort(list, pivot + 1,high);
high = pivot-1; /*尾递归*/
}
}
}
即判断左右子数组长度，选取较短的子数组先递归，较长的留在下一循环，并且进入下一循环后，先运行一次Partition，将较长的分割一段，再调用quickSort进行下一递归，较长的这一子数组再被缩短一次；而传统的，没有判断选取短的先进行，而且即便短的先进行，剩下的长的马上被调用quickSort进行递归。
同样考虑上一极端例子，假设每次分割的都是最大值，尾递归优化+两者取短的结合后，由于长度为1的数组先递归，调用quickSort进行递归，但一压栈进去，由于长度为一，就结束了，出栈了，再下一元素进栈出栈，依次这样直至完成，递归深度始终很浅。最坏情况下空间复杂度压缩至logn。
|