V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
这是一个专门讨论 idea 的地方。

每个人的时间,资源是有限的,有的时候你或许能够想到很多 idea,但是由于现实的限制,却并不是所有的 idea 都能够成为现实。

那这个时候,不妨可以把那些 idea 分享出来,启发别人。
tioover
V2EX  ›  奇思妙想

一个想法 基于随机的 排序辅助算法

  •  
  •   tioover · 2012-12-17 10:37:23 +08:00 · 2794 次点击
    这是一个创建于 4344 天前的主题,其中的信息可能已经有所发展或是发生改变。
    比如说 很多排序算法最坏情况是完全或者基本逆序,这时候可以在排序前随机取若干个值 通过值和索引是否是大致成正比 还是成反比还是没有规律 来判断用什么方向排序
    从概率上来说随机取得值是特殊的几乎是不可能的 这样可以规避很多最坏情况

    如果是没有明显规律的列表,可以在某种情况下降低列表的混乱程度,通过上面随机取数据的过程估算出大致的范围和分布 然后不断随机取元素 判断这个元素在什么区间内出现的概率最大,再随机插入到那个区间内

    昨晚睡不着 想的 对算法什么的还没入门,不知有没有实用性
    3 条回复    1970-01-01 08:00:00 +08:00
    SErHo
        1
    SErHo  
       2012-12-17 11:40:08 +08:00
    很多排序算法都有利用随机数的改进,比如快排在寻找“标杆”的时候,这个“标杆”就可能是随机得出的。
    lookhi
        2
    lookhi  
       2012-12-17 14:46:52 +08:00
    多看论文 一些论文都退化成怎么尽快的找到那个需要的标杆
    tioover
        3
    tioover  
    OP
       2012-12-17 19:35:39 +08:00
    @SErHo
    @lookhi
    惭愧!
    看过快排,但是不记得有标杆
    可能是我没仔细或者忘了
    orz
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1256 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 17:57 · PVG 01:57 · LAX 09:57 · JFK 12:57
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.