algorithm - 平滑排序算法在哪里使用？

Question

在我的大学学习算法时，我遇到了一个叫做 Smoothsort 的算法。它是一种很棒的算法，因为它是一种自适应算法，时间复杂度可以从线性复杂度到线性复杂度不等，它也是一种就地算法。但是，该算法的资源非常稀缺，可用的资源很难理解。但是，我发布此问题的原因是了解用例以及何时应该使用以及何时不应该使用？

这就是我想知道的全部内容，非常感谢您回答或审查这个问题。

标签： algorithmsortingheapdijkstraheapsort

Answer 1

musl libc 使用 Smoothsort 来实现qsort()。库作者的这个 Stack Overflow 回答描述了原因：它是最坏情况 O(n log n)（不像 Quicksort）、就地（不像 mergesort）和自适应（不像 heapsort）。我认为 Smoothsort 并没有被太多地用于某些组合

• Smoothsort 是不稳定的，在实践中，稳定性往往比 in-place 更可取，因为这意味着在相等键存在的情况下排序顺序是完全确定的。musl 具有 C 标准所允许的不稳定的自由，并且设计目标之一是不分配内存，除非明确要求（strstr()例如，这就是 musl 不使用 KMP 的原因）。

  请注意，存在就地、稳定、O(n log n) 时间的排序算法，但常数因子太大而不实用。

• 自适应性更好，平滑排序比堆排序更复杂。

• Smoothsort 并不广为人知，因为它几乎没有出现在所有本科算法课程（甚至研究生课程——例如，我在学校里没有看到）。