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

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

  •  1
     
  •   olist · 2021-10-10 22:32:42 +08:00 via iPhone · 4829 次点击
    这是一个创建于 1124 天前的主题,其中的信息可能已经有所发展或是发生改变。
    新算法:
    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 条附言  ·  2021-10-10 23:59:38 +08:00
    第二个算法不是冒泡排序,也不是其它常见排序算法的标准写法。
    第 2 条附言  ·  2021-10-11 01:05:06 +08:00
    这个算法简单且好记,判断条件是小于号时是升序排序,大于号时是降序排序。但算法的正确性却不显而易见。
    23 条回复    2021-10-12 13:40:25 +08:00
    Kilerd
        1
    Kilerd  
       2021-10-10 22:35:34 +08:00
    思绪良久,新算法这个不是最弱鸡的排序方法吗?
    rrfeng
        2
    rrfeng  
       2021-10-10 22:43:19 +08:00 via Android
    ???
    iBugOne
        3
    iBugOne  
       2021-10-10 22:45:16 +08:00   ❤️ 1
    就是插入排序,但是多做了一倍的无用功
    Mohanson
        4
    Mohanson  
       2021-10-10 23:41:59 +08:00
    建议楼上 3 楼仔细看代码, 这算法很反直觉啊
    zzxxisme
        5
    zzxxisme  
       2021-10-10 23:44:16 +08:00   ❤️ 2
    1. 这个论文里面提到这个 新算法 的好处不是在于效率,而是在于它的简单性,以及它的 看上去不是那么正确 的特点,然后这个论文去证明它的正确性。这个算法的确最后把 A 数组进行了升序排序。
    2. 你说的第二个算法不是传统认为的冒泡… 冒泡每次 swap 的是相邻的两个数,而你的第二个算法是为`A[i]`找`A[i .. n]`的最小值。
    wangyu17455
        6
    wangyu17455  
       2021-10-11 00:04:56 +08:00
    这不就是没有优化过的冒泡排序
    olist
        7
    olist  
    OP
       2021-10-11 00:05:17 +08:00 via iPhone
    @iBugOne 哈哈,确实就是个低配版的插入排序。
    olist
        8
    olist  
    OP
       2021-10-11 00:14:23 +08:00 via iPhone
    @zzxxisme 你说出了我分享这个算法的原因:-)
    iAIR
        9
    iAIR  
       2021-10-11 02:05:25 +08:00   ❤️ 1
    我想叫熊瞎子掰苞米排序……见到更好的就把手上的扔地上
    Blanke
        10
    Blanke  
       2021-10-11 07:33:13 +08:00 via Android
    简单选择排序
    abysmalIQ
        11
    abysmalIQ  
       2021-10-11 07:53:00 +08:00
    这个比其他排序好记在哪?
    chendy
        12
    chendy  
       2021-10-11 08:48:06 +08:00
    感觉像选择排序
    选择排序是记住下标最后换,这个是不记下标一直换
    Junzhou
        13
    Junzhou  
       2021-10-11 09:24:21 +08:00
    即使易于记忆,但是没什么实用性。面试快排,写业务调封装。
    9c04C5dO01Sw5DNL
        14
    9c04C5dO01Sw5DNL  
       2021-10-11 09:42:30 +08:00
    第二个是选择排序,每轮选择最小的排在左侧,跟标准写法比 swap 次数多了。

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

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

    这样写其实也是一样的
    krapnik
        18
    krapnik  
       2021-10-11 11:06:47 +08:00
    xianzhe
        19
    xianzhe  
       2021-10-11 16:42:31 +08:00
    我见过最骚的排序是睡觉排序。列表中每个元素都开新线程,然后睡上元素值大小的时间,到点输出。
    vone
        20
    vone  
       2021-10-11 17:28:54 +08:00
    还是 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  
       2021-10-11 17:49:43 +08:00
    @xianzhe 被这个惊到了,感觉是段子
    dafen7
        22
    dafen7  
       2021-10-12 10:54:24 +08:00
    @tfdetang 这应该就是段子,老程序员面试段子了
    wzzb
        23
    wzzb  
       2021-10-12 13:40:25 +08:00
    这应该是最“反直觉”的排序算法吧,没暖用是真的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5374 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 08:58 · PVG 16:58 · LAX 00:58 · JFK 03:58
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.