如何实现奇点排序和插入排序的优化混合排序算法？

Question

我想要切换到插入排序对较小的数组和快速排序的较大数组。切换到插入排序可以减少递归的次数。我想知道数组的最大大小，在那里我可以切换到插入排序.

以下是快速排序和插入排序的实现。对于数组长度<9，使用插入排序。https://megocode3.wordpress.com/2008/01/28/8/

即使我们知道双枢轴快速排序使用插入排序数组较小的数组长度< 27 http://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf

PS - Java使用双枢轴快速排序来排序原语类型。

Answer 1

我不太明白你的问题。在某种程度上，您决定从快速排序切换到插入排序，以节省内存，但牺牲了速度。插入排序是O(n^2)，而快速排序是O(nlogn)，但是快速排序使用递归，因此相对占用内存。根据您希望程序平衡的方式，决定在哪一点上通过减慢内存来节省内存，这取决于您。