我正在努力找出一个有效的quicksort算法.它工作正常,但是当元素数量巨大时,需要很长时间才能运行,并且数组的某些部分是预先排序的.我正在查阅维基百科的文章,在quicksort那里我找到了这样写的:
为了确保最多使用O(log N)空间,首先递归到数组的较小一半,然后使用尾调用递归到另一个.
对于这种小阵列上的调用(即长度小于实验确定的阈值t),使用插入排序,其具有较小的常数因子并因此在小阵列上更快.这可以通过将这些数组保持未排序并在末尾运行单个插入排序传递来实现,因为插入排序有效地处理几乎排序的数组.在识别每个小段时单独插入排序会增加启动和停止许多小排序的开销,但避免浪费在多个段边界上比较密钥的工作量,由于快速排序过程的工作原因,这些密钥将按顺序排列.它还改善了缓存的使用.
我目前正在递归两个分区.知道如何实现第一个提示吗？何谓递归先入阵的小一半,并使用尾部调用递归到其他？其次,我如何insertion-sort在快速排序中实施？它是否总能提高效率,或者只有在阵列的某些部分进行预先排序时？如果是第二种情况,那么当然我无法知道何时会发生这种情况.那我insertion-sort什么时候应该包括？
我一直在阅读文章,描述如何通过使用尾递归版本来减少快速排序的空间复杂性,但我无法理解这是怎么回事.以下是两个版本:
QUICKSORT(A, p, r)
q = PARTITION(A, p, r)
QUICKSORT(A, p, q-1)
QUICKSORT(A, q+1, r)
TAIL-RECURSIVE-QUICKSORT(A, p, r)
while p < r
q = PARTITION(A, p, r)
TAIL-RECURSIVE-QUICKSORT(A, p, q-1)
p = q+1
(来源 - http://mypathtothe4.blogspot.com/2013/02/lesson-2-variations-on-quicksort-tail.html)
据我所知,这两个都会导致数组的左半部分和右半部分的递归调用.在这两种情况下,一次只处理一半,因此在任何时候只有一个递归调用将使用堆栈空间.我无法看到尾递归快速排序如何节省空间.
上面的伪代码取自文章 - http://mypathtothe4.blogspot.com/2013/02/lesson-2-variations-on-quicksort-tail.html文章中 提供的解释让我更加困惑 -
Quicksort对给定的子数组进行分区并继续递归两次; 一个在左子阵列上,一个在右侧.这些递归调用中的每一个都需要其自己的堆栈空间流.此空间用于在某种递归级别存储数组的索引变量.如果我们想象这是从执行的开始到结束发生的,我们可以看到堆栈空间在每一层加倍.
那么Tail-Recursive-Quicksort如何修复所有这些呢？
好吧,我们现在只对一个子阵列进行递归,而不是在两个子阵列上递归.这消除了在每个执行层加倍堆栈空间的需要.我们通过使用while循环作为执行相同任务的迭代控件来解决这个问题.我们只需更改同一组变量并对新变量使用单个递归调用,而不是需要堆栈为两个递归调用保存变量集.
在常规快速排序的情况下,我没有看到堆栈空间在每个执行层都是如何加倍的.
注意: - 文章中没有提到编译器优化.