快速排序最坏情况
我在网上搜索了一下，但没有找到太多，我的问题是关于维度为 n 的输入，快速排序算法中发生最坏情况的概率是多少）。我知道这是相当罕见的，但我想知道从数字上讲它有多少以及我们如何评估它。谢谢
I search a little bit online but I didn't find much, my question is on an input with dimension n, what's the probability of the worse case occurring in the quicksort algorithm). I know it's quite rare but I was wondering numerically speaking how much it was and how can we evaluate it. Thank you
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
快速排序的最坏情况是所选元素（枢轴）始终是剩余集合中最小/最大的元素。
要生成这样的序列 - 您需要递归地工作，每一步在最后一个主元的两侧创建两个数组，其中先前选择的主元是最大或最小的一个，因此 QS 的递归算法将数组拆分为最坏的情况是一侧为 0。
The worst case for quick sort, is when the chosen element (pivot) is always the smallest/biggest element in the remaining set.
To generate such sequence - you need to work recursively, each step creating two arrays on both sides of your last pivot, where the pivot which was chosen previously was the biggest or the smallest one, so the recursive algorithm of QS split the array into the worst case where one side was 0.