排序算法如何具有O(1)的空间复杂度？

Question

我正在学习不同的排序算法及其时间/空间复杂性,并发现冒泡排序和插入排序等算法的空间复杂度为O(1).

这让我感到很奇怪,因为可能最低的空间复杂度可能是O(n)(如,存储数据集所需的内存,仅此而已)？

Answer 1

空间复杂度实际上是算法使用的额外空间复杂度,即除了数据占用的初始空间之外所需的额外空间.除原始数据外,冒泡排序和插入排序仅使用恒定的额外空间,因此它们在空间复杂度方面为O(1).

Answer 2

排序算法通过分配恒定量的空间（例如用于迭代的几个变量等，与输入的大小不成比例）而具有空间复杂度 O(1)。

在空间方面不是 O(1) 的排序算法的一个例子是合并排序的大多数实现，它分配一个辅助数组，使其成为 O(n)。理论上，快速排序可能看起来像 O(1)，但调用堆栈像空间一样计数，因此据说它是 O(log n)。

具有 O(1) 空间复杂度的排序算法示例包括：选择排序、插入排序、shell 排序和堆排序。