quicksort算法相等元素怎样处理
Algorithms (4th Edition)2.3.3.3小节: Entropy-optimal sorting. 方法是三向切分的快速排序。更好实现3向切分的方法需要查看练习2.3.22.Quick3way.java
■网友
这个看怎么实现快排了，如果是一般教科书上的朴素实现，相当于一个两重循环，是退化的情况。
■网友
不随机划分的快排最差输入为正序或者倒序。全部相同的数据不论怎么划分，都可视为正序或者倒序。所以，为最差输入。
■网友
正常实现的快排都是三分成 \u0026lt; , = , \u0026gt; ，实现上没什么很大的差别。因此这种输入无论如何都是一遍结束，是best case。不过这种输入没什么意义了，因此一般测试的时候都不会用这种input。
■网友
大量的相同元素会让Naive版本的快速排序退化到 O（n^2)Dutch national flag problem这个分割元素的方法可以解决这个问题。
■网友
如果是二分成的实现的话， 好的处理方式是相等元素也参与交换， 虽然可能会增加总的交换次数， 但是如果不参与交换可能会导致非常糟糕的性能， 一个例子就是你说的元素全相等的情况， 这样整个算法立马就会退化成一个 O(N^2) 算法。看有一点大家都没提， 就是虽然元素全相等的情况不太可能会发生， 但是在实际应用当中， 10000 个元素里有几千个元素相等这种情况， 未必是小概率事件以前写过一篇文章详细分析过这个问题， 有兴趣可以一起讨论: http://cifer.me/2016/07/24/quick-sort/
■网友
话说全部相等的话也可以视为乱序吧？也可以搞成标准的nlognint k=a;while(l\u0026lt;=r)｛while(l\u0026lt;=r){if(a\u0026lt;=k){swap(a,a);break;}--r;} while(l\u0026lt;=r){ if(a\u0026gt;=k){swap(a,a);break;} ++l; } if(l==r) break;｝
推荐阅读
- 为啥这个算法误差的看起来这么小
- 使用算法帮助人们筛选reader的信息是否存在可能
- 请问如果想成为算法工程师的话，大学选专业是选软件工程好还是计算机科学与技术好。
- 神经网络算法是否真的属于人工智能范畴
- 以算法为例，是否存在讲解者认为“懂得自然懂了，不懂的我说再多也白搭”的心理
- 豆瓣FM的推荐算法还有哪些可以改进的地方
- 如果已确定图像中物体的位置， 常用的目标分割和提取算法有哪些
- 出行管理|3座电动车满街跑的城市，都是南方城市，电动车快要与人数相等
- 请问只靠优化软件可以提高手机信号质量吗就是说不改变基带芯片和天线设计，信号质量可以靠算法优化吗
- 网络台球的动量算法规则是咋写的