这个算什么排序算法啊?

[zhanglintc]

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

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]

中学生？
你看的算法教材里面，难道没写每个算法在不同情况下的复杂度么？

[thedrwu]

一般叫做交换排序。。swap sort

[thedrwu]

也许你把冒泡提前喀嚓了，就会比这个快

[Perry]

两个 O(n^2) 的算法用秒表比较谁更快？

[zhanglintc]

@thedrwu 嘿，真是叫交换排序

[Ehend]

这想法和插入排序一样吧

[zhanglintc]

@Perry 是没多大意思，但是感觉反正俩都是 O(n^2)，随手写的时候还不如用第一个简单点，冒泡其实还挺麻烦的...

[zhanglintc]

@Ehend 我看着跟选择排序挺像的，选择排序里层循环只是维护一个 min 值，不用做那么多次交换，只需要最后把 min 值和下标 i 的值交换下就行了

[thedrwu]

不过你这个冒泡实现得不合理。竟然不是一冒到底。
更可怕的是我竟然为了暂时逃避工作来回这种帖子。。

[zhanglintc]

@thedrwu 这是我从维基百科扒拉下来的冒泡...

[raaaaaar]

找个时间把基础的排序算法学一遍吧

[JJstyle]

@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]

这真的不是选择排序吗？