algorithm - 如何优化快排

Question

我正在尝试制定一个高效的 quicksort 算法。它工作正常，但当元素数量巨大且数组的某些部分已预先排序时需要很长时间才能运行。我正在查找关于 quicksort 的维基百科文章，在那里我发现了这样写的:

To make sure at most O(log N) space is used, recurse first into the smaller half of the array, and use a tail call to recurse into the other.

Use insertion sort, which has a smaller constant factor and is thus faster on small arrays, for invocations on such small arrays (i.e. where the length is less than a threshold t determined experimentally). This can be implemented by leaving such arrays unsorted and running a single insertion sort pass at the end, because insertion sort handles nearly sorted arrays efficiently. A separate insertion sort of each small segment as they are identified adds the overhead of starting and stopping many small sorts, but avoids wasting effort comparing keys across the many segment boundaries, which keys will be in order due to the workings of the quicksort process. It also improves the cache use.

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

Answer 1

在 Quick-sort 中，您选择一个随机枢轴将数组划分为两半，大多数情况下一个可能更小，

例如数组大小 100，主元将数组分隔为 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

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