老师用链表实现快速排序的时间和空间复杂度是多少呢

来源：3-7 双路快速排序法

野源新之助

2019-11-13

写回答

1回答

liuyubobobo

2019-11-13

通常不会基于链表结构实现快排。这是因为快排需要随机化随机化标定点一步，在链表的结构下，不能 O(1) 的完成。

但是，如果一定要基于链表实现快排，平均复杂度也是 O(nlogn) 的。可以先使用 O(n) 的时间随机化标定点，基于这个标定点，partition 的复杂度也是 O(n) 的。整体，快排的时间复杂度依然是 O(nlogn) 的。

继续加油！：）

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1