一道数据结构题，为什么希尔排序的空间复杂度为O(1)，这个是怎么理解的？求指点，另外快速排序的

Question

空间复杂度为O(logn)怎么理解？求指点，谢谢

Answer 1

希尔排序是插入排序的改良版，插入排序空间复杂度就是O1，因为每次就是拿起一个数比较。
快速排序空间复杂度说的是 维持这个哨兵元素的空间。
因为快排是通过哨兵来划分左右数组，直到划分成有序为止。假设一个平均情况，第一次划分出一半一半，第二次在一半中划分出一半的一半也就是两个四分之一， 以此类推，那么需要logn次能把最左边的划分做完，也就是Logn个哨兵。 当你做完左边也就可以空出位置做右边，这时候也是logn , 空间是没增加的。