这个叫什么排序算法?

Question

冒泡排序貌似算是最出名的排序算法之一了，但是我感觉它的实现其实并不是正常人第一时间能想到的。反正就我来说，我能第一时间想到的排序算法长这样:

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[:])

结果：

running [py.py] ...

normal: 1.0199034214019775 secs
bubble: 1.4529473781585693 secs

Press ENTER or type command to continue

数据量再大点更明显，noraml 就没有比 bubble 慢过。一个更容易想到的而且比冒泡更快的算法难道不配拥有一个名字么。。。

Answer 1

Swap sort，翻译过来就是交换排序。

单从算法的角度来说，程序的运行时间不能用来评判算法优劣，评价算法还得从迭代次数和占用的最大内存来讲，因为个别算法由于利于 CPU 的计算，在同样的迭代次数和内存占用下可以更好地发挥 CPU 的作用。
交换排序的迭代次数恒为O(n2)，哪怕你已经给它排好了，它还是要迭代这么多次。
冒泡排序的迭代次数就得看情况，最好的情况是不需要排序的时候，只需要从头到尾扫描一遍就停止，为 O(n)，最坏的情况则是 O(n2)。

在相近的迭代次数下，交换排序的效率吊打冒泡，可能原因有二：

1. 冒泡的内循环次数不定， CPU 无法完全预测下一次的操作数，所以 CPU 的分支预测不能很好地发挥加速作用，而交换排序可以很好地利用分支预测给自己加速；
2. 冒泡排序的单次迭代操作比较麻烦，比如指针j到 j+1 的移位，这些操作会使得迭代所需时间变长。