如何优化快速排序

Question

我正在努力找出一个有效的quicksort算法.它工作正常,但是当元素数量巨大时,需要很长时间才能运行,并且数组的某些部分是预先排序的.我正在查阅维基百科的文章,在quicksort那里我找到了这样写的:

为了确保最多使用O(log N)空间,首先递归到数组的较小一半,然后使用尾调用递归到另一个.

对于这种小阵列上的调用(即长度小于实验确定的阈值t),使用插入排序,其具有较小的常数因子并因此在小阵列上更快.这可以通过将这些数组保持未排序并在末尾运行单个插入排序传递来实现,因为插入排序有效地处理几乎排序的数组.在识别每个小段时单独插入排序会增加启动和停止许多小排序的开销,但避免浪费在多个段边界上比较密钥的工作量,由于快速排序过程的工作原因,这些密钥将按顺序排列.它还改善了缓存的使用.

我目前正在递归两个分区.知道如何实现第一个提示吗？何谓递归先入阵的小一半,并使用尾部调用递归到其他？其次,我如何insertion-sort在快速排序中实施？它是否总能提高效率,或者只有在阵列的某些部分进行预先排序时？如果是第二种情况,那么当然我无法知道何时会发生这种情况.那我insertion-sort什么时候应该包括？

Answer 1

在快速排序中,您选择一个随机数据透视表,将数组分隔为两半,即大多数可能更小的机会,

例如,数组大小为100,pivot将数组分隔为40/60,40为较小的大小.

让我们假设您决定使用插入排序为10的阈值大小,您需要通过pivot继续递归拆分数组,只要其中一半变小或等于10,您可以使用行为类似的插入排序小尺寸阵列上的O(n).

考虑到如果您的数组反向排序(最坏的情况),插入排序将表现不佳.

关于递归的东西,你只需要修改快速排序递归的停止案例 - >数组大小<= 10停止递归,并使用插入排序对所有数组(在此递归步骤中小得多)进行排序.

通过尾递归,它们意味着用前半部分做你需要的一切,然后作为最后一个方法调用较小的一半的插入排序,它用于节省空间.

  Quick-sort()
      choose a pivot
      move the smaller elements from left
      move the bigger elements from right
      quick-sort on the bigger half of the array

      if half is less then X
         only then do an insertion sort on the other half <- this is a tail recursion insertion sort 
      else
         quick sort on this half also

据我所知,第二个优化建议不要对每个递归步骤使用插入排序,但要记住为其制定约束的索引,然后在一个批处理中连接所有切片中的项目时调用插入排序,这将确保改进缓存使用,但实现起来稍微困难一些,

Answer 2

有多种方法可以使标准的快速排序更有效率.要从帖子中实现第一个提示,您应该写一些类似于:

void quicksort(int * tab, int l, int r)
{
   int q;
   while(l < r)
   {
      q = partition(tab, l, r);
      if(q - l < r - q) //recurse into the smaller half
      {
         quicksort(tab, l, q - 1);
         l = q + 1;
      } else
      {
         quicksort(tab, q + 1, r);
         r = q - 1;
      }
   }
}

希望足够清楚.下一步是实现您自己的堆栈(或使用您使用的任何语言内置的一些)而不是使用递归调用.示例(伪)代码:

void quicksort2(int * tab, int l, int r)
{
    int le, ri, q;
    init stack;
    push(l, r, stack);
    while(!empty(stack))
    {
        //take the top pair of values from the stack and set them to le and ri
        pop(le, ri, stack);
        if(le >= ri)
            continue;
        q = partition(tab, le, ri);
        if(q - le < ri - q) //smaller half goes first
        {
            push(le, q - 1, stack);
            push(q + 1, ri, stack);
        } else
        {
            push(q + 1, ri, stack);
            push(le, q - 1, stack);
        }
    }
    delete stack;
}

然后,您可以继续执行帖子中的其他提示.要做到这一点,你应该设置一些任意常量,让我们称之为CUT_OFF,到20左右.这将告诉你的算法什么时候应该切换到插入排序.它应该是相当容易的(添加一个if语句的问题)来改变前面的例子,以便在它达到CUT_OFF点后切换到插入排序,所以我将离开你.

至于分区方法,我建议使用Lomuto分区而不是Hoare.

但是,如果您的数据已经预先排序,那么您可以考虑使用不同的算法.根据我的经验,如果您的数据是预先排序的,那么在链表上实现的自然系列合并排序是一个非常好的选择.

Answer 3

前段时间我写了一个基于快速排序的算法，你可以在那里找到（实际上它是一个选择算法，但也可以用作排序算法）：

• http://processors.wiki.ti.com/index.php/Top_K_Elements_Sort_For_DSP_With_Index_Ordering

我从这次经历中学到的教训如下：

1. 仔细调整算法的分区循环。这通常被低估了，但是如果您注意编写编译器/CPU 将能够软件流水线的循环，您确实会获得显着的性能提升。仅此一项就导致了大约 50% 的 CPU 周期的胜利。
2. 手动编码小类给你一个主要的性能胜利。当分区中要排序的元素数量低于 8 个元素时，不要费心尝试递归，而是仅使用 ifs 和 swaps 实现硬编码排序（查看此代码中的 fast_small_sort 函数） . 这可以导致大约 50% 的 CPU 周期获胜，使快速排序具有与编写良好的“合并排序”相同的实际性能。
3. 当检测到“不良”枢轴选择时，花时间选择更好的枢轴值。每当枢轴选择导致一侧低于要排序的剩余元素的 16% 时，我的实现就开始使用“中位数”算法进行枢轴选择。这是快速排序最坏情况性能的缓解策略，有助于确保在实践中上限也是 O(n*log(n)) 而不是 O(n^2)。
4. 优化具有大量相等值的数组（需要时）。如果要排序的数组有很多相等的值，则值得优化，因为它会导致主元选择不佳。在我的代码中，我通过计算所有等于枢轴值的数组条目来实现。这使我能够以更快的方式处理数组中的枢轴和所有相等值，并且在不适用时不会降低性能。这是针对最坏情况性能的另一种缓解策略，它通过大幅降低最大递归级别来帮助减少最坏情况堆栈的使用。

我希望这会有所帮助，洛朗。