关于课程示例代码中快速查找指定位置元素的效率问题

来源：3-9 归并排序和快速排序的衍生问题

慕粉3169703

2019-01-22

老师，我研究了您这一小节关于快速查找元素的代码，产生了一个疑问，如果遇到一个存在大量重复元素的数组，如果采用那种partition的做法，查找元素的效率是不是会受到比较大的影响。如果采用二路快排或者三路快排过程进行查找，效率是不是更优呢

写回答

1回答

liuyubobobo

2019-01-23

已采纳

抱歉，我不太了解你说的是哪个快速查找代码？

课程中已经介绍了，我们之所以引入二路快排或者三路快排，就是因为在面对包含大量重复元素的数组，一路快排是会稳定的退化成为O(n^2)算法的。所以如果有大量重复元素，一定要使用二路快排或者三路快排的思路：）

慕粉3169703

没问题，关于这一小节快速排序查找第N大的元素，我用的是三路快排的做法

2019-01-23

共1条回复

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

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

11187 学习 · 1614 问题

相似问题

回答 3

回答 1

回答 1

回答 4

回答 1