algorithm - 以下排序算法对什么样的输入数据有利/不利？

Question

以下排序算法对什么样的数据输入有效/无效？快速排序、归并排序、堆排序、插入排序等

我知道至少有 2 个因素会影响排序算法的性能:1) 输入的大小，以及 2) 数据是否已经大部分排序。但我不确切知道这些因素如何影响算法的效率。

我想详细研究一下，所以如果有任何来源/链接可以指给我看，那就太好了。

Answer 1

假设快速排序基于 Hoare 分区方案(中间值作为基准)，那么对于几乎已排序的数据，它不会降级到 O(n^2) 的最坏情况时间复杂度。

https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme

合并排序总是执行 n ⌈log2(n)⌉ 步。如果数据已经排序，则比较的次数约为 (⌈n ⌈log2(n)⌉)/2。

堆排序时间复杂度保持大致相同(重复可能会减少运行时间)。

插入排序是此列表中唯一在数据接近排序时速度更快的排序，但它的时间复杂度为 O(n^2)。我在想，对于几乎已排序的数据，时间复杂度将是 ~ O(m n)，其中 m 是错位的元素数。

自然合并排序的变体，可能在扫描和识别已排序的运行时对小运行使用插入排序，对已排序的数据的时间复杂度为 O(n)。