有大佬能帮忙解决一下这个问题嘛,想了很久都没做对....
快速排序算法选取轴点时可以采取不同的策略,本题试图说明“三者取中”的策略比随机选取的策略倾向于得到更平衡的轴点
设待排序序列的长度n很大,若轴点的选取使得分割后长/短子序列的长度比大于9:1,则称为不平衡
问题:针对不同的轴点选取策略,估计其发生不平衡的概率(请填十进制小数):
1. 从n个元素中等概率随机选取一个作为轴点:
2. n个元素中等概率选取三个元素,以它们的中间元素作为轴点:
(提示:如果不想笔算,可以编程模拟,结果与理论答案之间的误差在10%内即可)