如何做到O(1)空间快速排序？

ppip @ 2023-02-27 19:52:00

by poly @ 2023-02-27 19:55:10

应该是 O(1) 额外空间吧
直接做就可以

by TernaryTree @ 2023-02-27 19:55:19

这是能做到的吗。

by 蒟酱 @ 2023-02-27 19:56:59

这是能做到的吗，递归带了 log。

by TernaryTree @ 2023-02-27 19:59:02

递归的话栈空间是不是 log 的

by ppip @ 2023-02-27 19:59:51

那岂不是说快排不如归并/堆排，后两者都有原 O(1) 空间的实现方式

by chenxinyang2006 @ 2023-02-27 19:59:54

听说有 O(n \log^2 n) 时间 O(1) 额外空间的归并排序

by ud2_ @ 2023-02-27 20:02:39

如果输入是数组那么用堆排，如果是链表那么用归并。

by a2lyaXNhbWUgbWFyaXNh @ 2023-02-27 20:06:36

@ppip 堆排序。

原地建堆。

by fengziyi @ 2023-02-27 20:10:17

@ppip 是不如堆排，但是省空间的归并是 O(n\log n^2) 的，详见 oiwiki

by fengziyi @ 2023-02-27 20:14:56

参考 std::sort()
对于这玩意它的空间复杂度介于快排和堆排之间，因为它使用了两种算法的杂交（？
口胡一下，我认为 O(1) 的 qsort 不存在