排序算法中的截止值是什么？

Question

我被要求做快速排序，用插入排序切断。但我不明白截止值的含义。我需要有人用现实世界的例子来阐述这个概念。

Answer 1

一些算法在渐近上优于其他算法。在您的情况下，Quicksort 的渐近运行时间是 O(N(logN)) 而插入排序的渐近运行时间是 O(N^2)。

这意味着对于较大的 N 值，快速排序将比插入排序运行得更快。

但是，对于较小的 N 值，插入排序可能运行得更快。因此，您可以通过将 Quicksort 与小数组大小的插入排序相结合来优化 Quicksort 的实际运行时间。

快速排序是一种递归算法，它将原始数组分解为更小的数组，并在每个子数组上递归运行。插入排序截断意味着一旦数组大小小于某个恒定截断大小，就使用插入排序对这些小数组进行排序，而不是继续递归。

Answer 2

如果没有看到确切的需求说明，就很难确定。

但是，我认为这意味着您应该使用O(N^2)低于特定大小（“截断”）的插入排序 ( ) 和O(NlogN)高于该大小的快速排序 ( )。

• 它们可能意味着您对输入数组的大小进行此测试。

• 它们也可能意味着您实现了混合排序，并在快速排序分区大小小于阈值时对子数组使用插入排序。

两种解释都有道理。

---

我需要有人用现实世界的例子来阐述这个概念。

我怀疑您是否需要示例来理解这一点。如果您了解插入排序和快速排序算法，那么这在概念上很简单。（如果你不理解它们，有很多地方可以阅读它们，从你的数据结构和算法教科书开始。）