如何优化快速排序

Question

我正在努力想出一个高效的quicksort algo。它工作正常，但是当元素数量很大，并且数组的某些部分是预先排序的时候，运行起来需要很长的时间。我在quicksort上查找维基百科的文章，在那里我发现了这样的一篇文章：

为了确保最多使用O(log )空间，请先对数组的较小部分进行递归，然后使用尾调用对另一个数组进行递归。 使用插入排序，它具有较小的常数因子，因此在小数组上更快，用于调用这些小数组(即长度小于实验确定的阈值t)。这可以通过将这些数组保持未排序并在末尾运行一个插入排序传递来实现，因为插入排序有效地处理了几乎已排序的数组。在识别每个小段时，一个单独的插入排序增加了启动和停止许多小排序的开销，但避免了跨多个段边界比较键的浪费，这些键由于快速排序过程的工作而变得井然有序。它还改进了缓存的使用。

我目前正在对两个分区进行递归处理。知道如何实现第一个提示吗？什么是指递归首先进入数组的较小部分，然后使用尾调用递归到另一个？其次，如何在快速排序中实现insertion-sort？它是总是提高效率，还是只有当数组的某些部分是预先排序的时候？如果是第二种情况，那么我当然无法知道什么时候会发生这种情况。那么我什么时候应该包括insertion-sort

Answer 1

在快速排序中，您选择一个随机的枢轴将数组划分为两个半的，其中一个可能更小，

例如，数组大小为100，枢轴将数组分隔为40 / 60，40为较小的大小。

假设您决定了使用插入排序为10的阈值大小，则需要继续递归地按枢轴拆分数组，每当其中一半的值变小或等于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点后切换到插入排序，所以我将让您继续这样做。

至于分区方法，我建议使用洛穆托分区而不是Hoare。

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

Answer 3

不久前，我编写了一个基于快速排序的算法，您可以在那里找到它(实际上它是一个选择算法，但也可以使用一个排序算法)：

• 排序

我从这次经验中吸取的教训如下：

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

我希望这能帮上忙洛朗。