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

这个算什么排序算法啊?

  •  
  •   zhanglintc · 2020-08-26 22:50:25 +08:00 · 1799 次点击
    这是一个创建于 1310 天前的主题,其中的信息可能已经有所发展或是发生改变。

    我觉得这个大概是最容易想到的排序算法了吧(比冒泡更容易想到吧?)

    def normal(a):
        for i in range(len(a)):
            for j in range(i, len(a)):
                if a[i] > a[j]:
                    a[i], a[j] = a[j], a[i]
    

    但是这个算法有名字么... 而且我试了下, 这个算法比冒泡更快:

    def timer(func):
        import functools
        @functools.wraps(func)
        def wrapper(*args, **kwargs):
            import time
            t1 = time.time()
            func(*args, **kwargs)
            t2 = time.time()
            print(f"{func.__name__}: {t2 - t1} secs")
        return wrapper
    
    @timer
    def bubble(a):
        for i in range(len(a)):
            for j in range(len(a) - i - 1):
                if a[j] > a[j + 1]:
                    a[j], a[j + 1] = a[j + 1], a[j]
    
    @timer
    def normal(a):
        for i in range(len(a)):
            for j in range(i, len(a)):
                if a[i] > a[j]:
                    a[i], a[j] = a[j], a[i]
    
    import random
    a = [random.randint(0, 100000) for x in range(2000)]
    
    normal(a[:])
    bubble(a[:])
    

    结果(试了很多次了, 数据量大更明显, normal 就没有比 bubble 更慢过):

    running [py.py] ...
    
    normal: 1.0199034214019775 secs
    bubble: 1.4529473781585693 secs
    
    Press ENTER or type command to continue
    

    所以各位, 这个算法有名字么... 为什么这个算法既容易想到, 又比冒泡快, 却没有冒泡出名呢...

    across
        1
    across  
       2020-08-26 22:53:49 +08:00
    中学生?
    你看的算法教材里面,难道没写每个算法在不同情况下的复杂度么?
    thedrwu
        2
    thedrwu  
       2020-08-26 22:55:04 +08:00 via Android
    一般叫做交换排序。。swap sort
    thedrwu
        3
    thedrwu  
       2020-08-26 22:56:55 +08:00 via Android
    也许你把冒泡提前喀嚓了,就会比这个快
    Perry
        4
    Perry  
       2020-08-26 23:00:25 +08:00 via iPhone   ❤️ 1
    两个 O(n^2) 的算法用秒表比较谁更快?
    zhanglintc
        5
    zhanglintc  
    OP
       2020-08-26 23:03:34 +08:00 via iPhone
    @thedrwu 嘿,真是叫交换排序
    Ehend
        6
    Ehend  
       2020-08-26 23:05:14 +08:00 via Android
    这想法和插入排序一样吧
    zhanglintc
        7
    zhanglintc  
    OP
       2020-08-26 23:06:07 +08:00 via iPhone
    @Perry 是没多大意思,但是感觉反正俩都是 O(n^2),随手写的时候还不如用第一个简单点,冒泡其实还挺麻烦的...
    zhanglintc
        8
    zhanglintc  
    OP
       2020-08-26 23:08:19 +08:00 via iPhone
    @Ehend 我看着跟选择排序挺像的,选择排序里层循环只是维护一个 min 值,不用做那么多次交换,只需要最后把 min 值和下标 i 的值交换下就行了
    thedrwu
        9
    thedrwu  
       2020-08-26 23:08:20 +08:00 via Android
    不过你这个冒泡实现得不合理。竟然不是一冒到底。
    更可怕的是我竟然为了暂时逃避工作来回这种帖子。。
    zhanglintc
        10
    zhanglintc  
    OP
       2020-08-26 23:11:11 +08:00 via iPhone
    @thedrwu 这是我从维基百科扒拉下来的冒泡...
    raaaaaar
        11
    raaaaaar  
       2020-08-26 23:24:17 +08:00 via Android
    找个时间把基础的排序算法学一遍吧
    JJstyle
        12
    JJstyle  
       2020-08-27 00:07:46 +08:00
    @zhanglintc #8 这就是选择排序吧,内循环没必要立即交换两个元素的,所以你的排序比一般的选择排序性能差一些。

    有人说这个冒泡排序我也是笑了,冒泡排序两个特点:1. 从大到小排序; 2. 相邻比较,哪条满足了?

    改写了一下:

    ```python
    def normal(a):
    for i in range(len(a)):
    min = i
    for j in range(i, len(a)):
    if a[min] > a[j]:
    min = j
    if (min != i):
    a[min], a[i] = a[i], a[min]
    return a
    ```
    agagega
        13
    agagega  
       2020-08-27 20:54:58 +08:00
    这真的不是选择排序吗?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1001 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 19:59 · PVG 03:59 · LAX 12:59 · JFK 15:59
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.