V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
olist
V2EX  ›  程序员

今天看到一个新发现的有趣的排序算法。

  •  1
     
  •   olist · 50 天前 via iPhone · 3679 次点击
    这是一个创建于 50 天前的主题,其中的信息可能已经有所发展或是发生改变。
    新算法:
    for i = 1 to n do
    for j = 1 to n do
    if A[i] < A[j] then
    swap A[i] and A[j]

    等价的冒泡排序算法:
    for i = 1 to n do
    for j = i + 1 to n do
    if A[i] > A[j] then
    swap A[i] and A[j]

    算法来源: https://arxiv.org/pdf/2110.01111.pdf
    第 1 条附言  ·  50 天前
    第二个算法不是冒泡排序,也不是其它常见排序算法的标准写法。
    第 2 条附言  ·  50 天前
    这个算法简单且好记,判断条件是小于号时是升序排序,大于号时是降序排序。但算法的正确性却不显而易见。
    23 条回复    2021-10-12 13:40:25 +08:00
    Kilerd
        1
    Kilerd   50 天前
    思绪良久,新算法这个不是最弱鸡的排序方法吗?
    rrfeng
        2
    rrfeng   50 天前 via Android
    ???
    iBugOne
        3
    iBugOne   50 天前   ❤️ 1
    就是插入排序,但是多做了一倍的无用功
    Mohanson
        4
    Mohanson   50 天前
    建议楼上 3 楼仔细看代码, 这算法很反直觉啊
    zzxxisme
        5
    zzxxisme   50 天前   ❤️ 2
    1. 这个论文里面提到这个 新算法 的好处不是在于效率,而是在于它的简单性,以及它的 看上去不是那么正确 的特点,然后这个论文去证明它的正确性。这个算法的确最后把 A 数组进行了升序排序。
    2. 你说的第二个算法不是传统认为的冒泡… 冒泡每次 swap 的是相邻的两个数,而你的第二个算法是为`A[i]`找`A[i .. n]`的最小值。
    wangyu17455
        6
    wangyu17455   50 天前
    这不就是没有优化过的冒泡排序
    olist
        7
    olist   50 天前 via iPhone
    @iBugOne 哈哈,确实就是个低配版的插入排序。
    olist
        8
    olist   50 天前 via iPhone
    @zzxxisme 你说出了我分享这个算法的原因:-)
    iAIR
        9
    iAIR   50 天前   ❤️ 1
    我想叫熊瞎子掰苞米排序……见到更好的就把手上的扔地上
    Blanke
        10
    Blanke   50 天前 via Android
    简单选择排序
    abysmalIQ
        11
    abysmalIQ   50 天前
    这个比其他排序好记在哪?
    chendy
        12
    chendy   50 天前
    感觉像选择排序
    选择排序是记住下标最后换,这个是不记下标一直换
    Junzhou
        13
    Junzhou   50 天前
    即使易于记忆,但是没什么实用性。面试快排,写业务调封装。
    giiiiiithub
        14
    giiiiiithub   50 天前
    第二个是选择排序,每轮选择最小的排在左侧,跟标准写法比 swap 次数多了。

    第一个是循环次数比第二个要多的选择排序,不过是降序。。。。
    olist
        15
    olist   50 天前
    @giiiiiithub 第一个也是升序,是不是反直觉?
    giiiiiithub
        16
    giiiiiithub   50 天前
    @olist 擦,还真是,第一个不是选择排序。。。。。确实是一种没见过的排序方法
    njutree
        17
    njutree   50 天前
    这种思路感觉计算机发展这么多年早就有大佬想过了,证明正确性也不是很难。关键是这个思路没有暖用交换次数多效率极低,如果仅仅是为了简单:

    for i = 1 to n do
    for j = 1 to n do
    if A[i] > A[j] then
    swap A[i] and A[j]

    这样写其实也是一样的
    xianzhe
        19
    xianzhe   49 天前
    我见过最骚的排序是睡觉排序。列表中每个元素都开新线程,然后睡上元素值大小的时间,到点输出。
    vone
        20
    vone   49 天前
    还是 Bogo 排序更巧妙一点。

    https://zh.wikipedia.org/wiki/Bogo%E6%8E%92%E5%BA%8F
    https://z3.ax1x.com/2021/10/11/5ZwCg1.png

    Bogo 排序( bogo-sort )是个非常低效率的排序算法,通常用在教学或测试。其原理等同将一堆卡片抛起,落在桌上后检查卡片是否已整齐排列好,若非就再抛一次。其名字源自 Quantum bogodynamics,又称 bozo sort 、blort sort 或猴子排序(参见无限猴子定理)。
    伪代码:

    function bogosort(arr)
    while arr is not ordered
    arr := 随机排列(arr)

    其平均时间复杂度是 O(n × n!),在最坏情况所需时间是无限。它并非一个稳定的算法。
    tfdetang
        21
    tfdetang   49 天前
    @xianzhe 被这个惊到了,感觉是段子
    dafen7
        22
    dafen7   49 天前
    @tfdetang 这应该就是段子,老程序员面试段子了
    wzzb
        23
    wzzb   48 天前
    这应该是最“反直觉”的排序算法吧,没暖用是真的
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3719 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 62ms · UTC 03:54 · PVG 11:54 · LAX 19:54 · JFK 22:54
    ♥ Do have faith in what you're doing.