java - 排序算法中的截止值是多少？

Question

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

Answer 1

一些算法比其他算法渐近更好。在您的情况下，快速排序的渐近运行时间为 O(N(logN))，而插入排序的渐近运行时间为 O(N^2)。

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

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

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