排序算法如何具有 O(1) 的 space 复杂度？
How can a sorting algorithm have a space complexity of O(1)?
我正在学习不同的排序算法及其 time/space 复杂度，发现冒泡排序和插入排序等算法的 space 复杂度为 O(1)。
这让我觉得很奇怪，因为可能的最低 space 复杂度肯定是 O(n)（例如，存储数据集所需的内存，仅此而已）？
space 复杂度实际上是您的算法使用的 额外 space 复杂度，即您需要的额外 space，除了从最初的space开始被数据占用。冒泡排序和插入排序只使用一个常量附加space，除了原始数据，所以它们在space复杂度中是O(1)。
排序算法具有 space 复杂度 O(1)，通过分配恒定数量的 space，例如用于迭代的一些变量等，它们与排序的大小不成比例输入。
根据 space，排序算法不是 O(1) 的一个示例是合并排序的大多数实现，它分配一个辅助数组，使其成为 O(n)。 Quicksort 在理论上可能看起来像 O(1)，但调用堆栈计数像 space，因此据说是 O(log n).
复杂度为 O(1) space 的排序算法示例包括：选择排序、插入排序、shell 排序和堆排序。
Bottom-up 合并排序可以这样写，它只使用常量额外 space。这是渐近最优排序 (O(n*log(n))) 的示例，同时仅使用 O(1) space.
编辑：这个回答有点粗心。自底向上归并排序仅在链表上使用O(1)space。对于在数组上使用 O(1) space 的排序，堆排序是最好的选择。这是通过将数组就地变成最大堆来完成的，然后重复调用 delete-max 并将值存储在数组的后面。当堆为空时，对数组进行排序。
我正在学习不同的排序算法及其 time/space 复杂度，发现冒泡排序和插入排序等算法的 space 复杂度为 O(1)。
这让我觉得很奇怪，因为可能的最低 space 复杂度肯定是 O(n)（例如，存储数据集所需的内存，仅此而已）？
space 复杂度实际上是您的算法使用的 额外 space 复杂度，即您需要的额外 space，除了从最初的space开始被数据占用。冒泡排序和插入排序只使用一个常量附加space，除了原始数据，所以它们在space复杂度中是O(1)。
排序算法具有 space 复杂度 O(1)，通过分配恒定数量的 space，例如用于迭代的一些变量等，它们与排序的大小不成比例输入。
根据 space，排序算法不是 O(1) 的一个示例是合并排序的大多数实现，它分配一个辅助数组，使其成为 O(n)。 Quicksort 在理论上可能看起来像 O(1)，但调用堆栈计数像 space，因此据说是 O(log n).
复杂度为 O(1) space 的排序算法示例包括：选择排序、插入排序、shell 排序和堆排序。
Bottom-up 合并排序可以这样写，它只使用常量额外 space。这是渐近最优排序 (O(n*log(n))) 的示例，同时仅使用 O(1) space.
编辑：这个回答有点粗心。自底向上归并排序仅在链表上使用O(1)space。对于在数组上使用 O(1) space 的排序，堆排序是最好的选择。这是通过将数组就地变成最大堆来完成的，然后重复调用 delete-max 并将值存储在数组的后面。当堆为空时，对数组进行排序。