问题标签 [introsort]

Introsort从快速排序开始，当递归深度超过基于被排序元素数量的级别时，切换到堆排序。那个号码是多少？是否有特定范围或限制值？

我使用快速排序、堆排序实现了 introsort。我的手工编码版本基于 D. Musser 的建议，递归深度切换到作为参数传递的堆排序，中位数为 3 枢轴选择。切换到简单插入排序的元素阈值为 16。

我读过 C++ 对其内置的 std::sort 使用 introsort（内省排序），它从快速排序开始，当你达到深度限制时切换到堆排序。

我还读到深度限制应该是 2*log(2,N)。

这个值纯粹是实验性的吗？或者它背后有什么数学理论？

我正在阅读介绍排序。我了解其中的大部分内容，但我不明白为什么大多数实现倾向于对其中的快速排序部分进行一次递归。快速排序的标准实现使用两个递归进行快速排序。

在这里，我尝试将其修改为：

我做了两个修改，一个是我现在使用两个递归，第二个是我跳过了递归的枢轴元素，因为它已经在正确的位置。

无论有没有我的修改，程序似乎都运行良好。但我想知道为什么他们在大多数在线实现中使用单递归。

我目前正在研究排序算法，需要实现HeapSort和Introspective Sort。

我想我已经成功实现了 HeapSort（代码有效，尝试了数百万个随机大小的随机数组，总是有效），这是我的代码：

moveDown 代码是：

这两种方法应该工作得很好，我已经测试了很多次，我从来没有遇到任何问题。

我也试图从这两种方法开始并实现内省排序，我的代码是这样的：

我认为上面的代码也很好，假设方法 isort 和 hsortAux 工作正常。在我的测试中，我注意到它仅在调用 heapsort 时才会失败。当我使用 tukey 近似值来确定枢轴索引时，以及当我选择一个随机枢轴（例如总是数组的第一个元素）时，代码应该可以工作（目标是让它工作）。使用 QuickSort 的分区应该是正确的，因为我已经尝试了许多快速排序实现并且它们都可以工作，而且正如我已经说过的，当不调用 heapsort 时代码可以工作。分区实际上是另一种完美工作方法中快速排序的复制粘贴。

我确定方法 isort 和 tukeyApproximation 可以按预期工作，因为我已经单独测试了它们并在快速排序实现上进行了测试，它们工作得很好。

但是，我似乎无法实现仅在 min 和 max 之间的数组部分上完成其工作的堆排序（称为 hsortAux 的方法）。我花了几个小时在这里和谷歌上寻找答案，我试图通过查看其他人的代码来实现我自己的版本，但我多次失败，在这里我在浪费你的时间:)。一旦我设法进行了工作 heapSort 但当 tukey 近似值未选择枢轴时（例如数组的第一个元素或该部分中的随机元素），它似乎不起作用。

这是我当前的 hsortAux 代码，源自原始 hsortAux：

moveDownAux 应该是仅适用于数组部分的 moveDown 方法，但是我真的不知道如何实现它，我尝试使用以前的 moveDown 方法，但它显然根本不起作用。在实现 moveDownAux 时，我什至不确定是否需要名为min的变量。

这是我当前的 moveDownAux 方法：

提前感谢您的时间和答案

为了好玩，我正在尝试实现 Introsort 的迭代变体。默认实现如下所示：

我使用 的glibc实现qsort作为迭代 introsort 的基础，因为qsort碰巧实现了迭代快速排序。

我的实现如下所示：

10对于随机元素的大小输入，100'000它似乎运行良好，但是当我测试一百万个元素时，它突然减慢到几秒钟，这对于具有 100 万个元素的单个数组来说太长了。

我该如何解决？

我正在尝试了解 introsort 并找到稀缺的资源。我的理解是它使用快速排序，但是当递归变得很深时切换到堆排序。这是因为快速排序通常比堆排序快，除非调用深度变得很深。

我的问题是，切换到堆排序之前的深度是如何计算的？维基百科有floor(log(length_of_data))x2，但我见过其他的东西。原因是什么？我是否正确的算法想要坚持使用快速排序，直到由于内存原因需要切换到堆排序？

尝试使用 Python 实现 Introsort。

给出的伪代码是：

我的源代码是：

给出的结果是错误的：

似乎它在分区后立即停止并且对子列表的排序不起作用。很明显，21 是支点，分区工作得很好。

谁能指出我的错误？非常感谢你！

我并没有真正了解 Introsort 算法。如您所见，我添加了它的伪代码。最大深度是什么意思？

⌊log(length(A))⌋ × 2“ ”是什么意思

我希望有人能给我解释一下。

请解释为什么 C++ sort() 算法使用 introsort？以及在哪些情况下它比常规的 mergeSort 算法表现更好