qq_24778169 2018-07-03 12:11 采纳率: 33.3%
浏览 1612
已结题

一道关于快速排序三者取中的题

有大佬能帮忙解决一下这个问题嘛,想了很久都没做对....

快速排序算法选取轴点时可以采取不同的策略,本题试图说明“三者取中”的策略比随机选取的策略倾向于得到更平衡的轴点

设待排序序列的长度n很大,若轴点的选取使得分割后长/短子序列的长度比大于9:1,则称为不平衡

问题:针对不同的轴点选取策略,估计其发生不平衡的概率(请填十进制小数):
1. 从n个元素中等概率随机选取一个作为轴点:
2. n个元素中等概率选取三个元素,以它们的中间元素作为轴点:

(提示:如果不想笔算,可以编程模拟,结果与理论答案之间的误差在10%内即可)

  • 写回答

3条回答 默认 最新

  • alaboboy 2018-07-03 12:50
    关注

    策略1:0.8(这个不用说,0.1+0.1)
    策略2:三维坐标系内(0,0,0)和(1,1,1)间正方体,每坐标代表一数
    中间的元素在0.1--0.9之间的区域:(记 a 为0--0.1, b 为0.1--0.9 , c 为0.9--1)
    (0,0.1,0.1) 和 (0.1,0.9,0.9)之间正方体 (记为a,b,b) +
    (0,0.1,0.9) 和 (0.1,0.9,1)之间正方体 (记为a,b,c) +
    (a,c,b)+( b,a,b)+(b,a,c)+(b,b,a)+(b,b,b)+(b,b,c)+(b,c,a)+(b,c,b)+(c,a,b)+(c,b,a)+(c,b,b)
    共0.8 * 0.1 * 0.1 * 6+ 0.8 * 0.8 * 0.1 * 6+0.8^3=0.944,
    不平衡几率0.056

    评论

报告相同问题?

悬赏问题

  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗
  • ¥15 钢筋实图交点识别,机器视觉代码
  • ¥15 如何在Linux系统中,但是在window系统上idea里面可以正常运行?(相关搜索:jar包)
  • ¥50 400g qsfp 光模块iphy方案
  • ¥15 两块ADC0804用proteus仿真时,出现异常