堆排序的辅助Space和Space复杂度的区别？
Difference between Auxiliary Space and Space Complexity of Heap Sort?
Difference between Auxiliary Space and Space Complexity of Heap Sort?
我的尝试：
如解释的那样here：
如果我们想在 space 的基础上比较标准排序算法，那么辅助 Space 将是比 Space 复杂性更好的标准。归并排序使用O(n)辅助space，插入排序和堆排序使用O(1)辅助space。 Space 尽管所有这些排序算法的复杂度都是 O(n)。
我用谷歌搜索了堆排序的 space 复杂度，我发现 space 复杂度是 O(1)。
我的问题是：
Is that explanation correct? What is difference between Auxiliary Space and Space Complexity?
Auxiliary应该是指所有未用于存储原始输入的内存。
堆排序输入是一个无序元素的数组，它通过将它们重新排列就地来工作，这意味着没有（或者它的数量不变，即不依赖于大小input array) auxiliary space is used (heap is built using the input array - http://www.algostructure.com/sorting/heapsort.php).
谈到 space 复杂度你还应该考虑输入和辅助使用的 space，所以从这个意义上说，堆排序有 space 复杂度O(n)+O(1)（n 作为输入，1 作为辅助 space）。
公平地说，如果你愿意，你也可以考虑在堆栈上使用 space（堆排序的递归实现使用 space，尽管它应该只是 O(logn)，see here for more details） .
顺便说一下，merge-sort 的辅助 space 也可以是 O(1) 因为存在 merge-sort 的一个版本 对数组进行就地排序 (How to sort in-place using the merge sort algorithm?)。
Difference between Auxiliary Space and Space Complexity of Heap Sort?
我的尝试：
如解释的那样here：
如果我们想在 space 的基础上比较标准排序算法，那么辅助 Space 将是比 Space 复杂性更好的标准。归并排序使用O(n)辅助space，插入排序和堆排序使用O(1)辅助space。 Space 尽管所有这些排序算法的复杂度都是 O(n)。
我用谷歌搜索了堆排序的 space 复杂度，我发现 space 复杂度是 O(1)。
我的问题是：
Is that explanation correct? What is difference between Auxiliary Space and Space Complexity?
Auxiliary应该是指所有未用于存储原始输入的内存。
堆排序输入是一个无序元素的数组，它通过将它们重新排列就地来工作，这意味着没有（或者它的数量不变，即不依赖于大小input array) auxiliary space is used (heap is built using the input array - http://www.algostructure.com/sorting/heapsort.php).
谈到 space 复杂度你还应该考虑输入和辅助使用的 space，所以从这个意义上说，堆排序有 space 复杂度O(n)+O(1)（n 作为输入，1 作为辅助 space）。
公平地说，如果你愿意，你也可以考虑在堆栈上使用 space（堆排序的递归实现使用 space，尽管它应该只是 O(logn)，see here for more details） .
顺便说一下，merge-sort 的辅助 space 也可以是 O(1) 因为存在 merge-sort 的一个版本 对数组进行就地排序 (How to sort in-place using the merge sort algorithm?)。