答案取决于选择支点的策略。在早期版本的”
快速排序”
中, 最左边(或最右边)的元素被选择为枢轴, 在以下情况下会发生最坏的情况。
1)数组已按相同顺序排序。
2)数组已经按照相反的顺序排序。
【Quicksort最坏的情况何时发生()】3)所有元素都相同(情况1和2的特殊情况)
由于这些情况是非常常见的用例, 因此可以通过为枢轴选择一个随机索引, 选择分区的中间索引或(尤其是对于较长的分区)选择第一个, 中间和最后一个元素的中位数来轻松解决此问题。枢轴的分区。通过这些修改, 快速排序的最坏情况发生的机会较少, 但是如果输入数组使得始终选择最大(或最小)元素作为枢轴, 则最坏情况仍然会发生。
参考文献:
http://en.wikipedia.org/wiki/Quicksort
推荐阅读
- 脚本语言和编程语言有什么区别()
- 我们什么时候通过引用或指针传递参数()
- C++中什么时候使用初始化列表()
- MySQL事务
- Linux下如何使用 vmstat 命令
- MySQL日志管理
- go语言学习--函数
- #yyds干货盘点#ping(测试主机之间网络的连通性)
- 基于Vue3+Vite+TS,二次封装element-plus业务组件