排序为1/3的数组上的正常和随机快速排序
排序为1/3的数组上的正常和随机快速排序
提问于 2020-12-03 15:32:33
我试图计算在具有以下属性的数组上应用快速排序(随机或正常)的时间复杂度：
数组在前2/3中没有排序，最大的元素是t。
下一个1/3被排序，这里的所有元素都大于t\
我知道，在正常的快速排序中，选择这两个部分之间的屏障会导致不必对下一个1/3排序，但我无法找到一种形式(数学)方法来计算时间复杂性的渐近界。
提前感谢
回答 1
Stack Overflow用户
回答已采纳
发布于 2020-12-03 15:49:12
随机快速排序相当于先对数组进行洗牌，然后应用朴素的快速排序。洗牌需要线性时间，这样就可以得到快速排序的平均时间复杂度，而不考虑部分排序的输入，即O(n log )。
朴素快速排序在这些输入上将具有二次时间复杂度，因为最终元素t将被选择为支点，t发生在排序区域之前，因此该区域将被选择为一个完整的分区。朴素快速排序将在( n /3)中占用这个分区的二次时间，这在n中是二次的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/65129024
复制相关文章
相似问题
腾讯云开发者
