快速排序是一种不稳定排序,它的时间复杂度为O(n·lgn),最坏情况为O(n2);空间复杂度为O(n·lgn)
![图片[1]-快速排序最坏复杂度,最坏是什么情况-编程社](https://cos.bianchengshe.com/wp-content/uploads/2024/04/image-28.png?imageMogr2/format/webp/interlace/1/quality/100)
快速排序最坏的情况还得看枢轴(pivot)的选择策略。在快速排序的早期版本中呢,最左面或者是最右面的那个元素被选为枢轴,那最坏的情况就会在下面的情况下发生啦:
- 数组已经是正序(same order)排过序的。
- 数组已经是倒序排过序的。
- 所有的元素都相同(1、2的特殊情况)
因为这些案例在用例中十分常见,所以这个问题可以通过要么选择一个随机的枢轴,或者选择一个分区中间的下标作为枢轴,或者(特别是对于相比更长的分区)选择分区的第一个、中间、最后一个元素的中值作为枢轴。
有了这些修改,那快排的最差的情况就不那么容易出现了,但是如果输入的数组最大(或者最小元素)被选为枢轴,那最坏的情况就又来了。
© 版权声明
文章版权归作者所有,未经允许请勿转载。
THE END
暂无评论内容