O(n^2)系列

一般人第一次接触到的排序算法应该都是 O(n^2) 等级的吧。常见的有冒泡排序，选择排序，插入排序···

¶冒泡排序 Bubble sort

冒泡排序是利用两层循环不断地将数据中比较大的数字交换到最上面来，看上去就像水中的气泡冒出来一样。

想法很简单，实现起来也是如此。循环中，看到循序不一样的就交换一次。

def bubble_sort(data):
    """Bubble sort

    Args:
        data (List[int]): 待排列表

    Returns:
        List[int]: 有序列表
    """
    length = len(data)

    for i in range(length):
        for j in range(i + 1, length):  # 从i + 1开始 减少循环次数
            if data[i] &lt; data[j]:  # 从大到小 如果反了交换
                data[i], data[j] = data[j], data[i]

    return data

是不是很直接，当然效率也是很感人··· 在我这个小奔腾上面进行, 进行10000个数据的排序就要10秒左右(9.5665s)。

在第13行上，range(i + 1, length) 循环从i + 1开始而不是从0或者i开始，是为了提高效率，因为我们知道第一层循环是从第一个元素开始的，开头的i个元素是有序的，就不需要进行大小比较了，而第range(x, y)的循环范围是[x, y)，第i个不需要重复比较，因为就是它本身。可以看到Python本身神奇的 **tuple assignment **功能用在了交换数组数据上面，简单清晰。

总共需要进行近n^2，这么多次的排序操作，二次函数增长可是很快的。

我们可以在每次循环结束的时候添加一个打印操作，显示当前进行的状态，比如这是10个元素[3, 5, 4, 8, 2, 7, 6, 0, 9, 1]的排序过程，每次交换输出一行:

调用函数: bubble_sort
[5, 3, 4, 8, 2, 7, 6, 0, 9, 1]
[8, 3, 4, 5, 2, 7, 6, 0, 9, 1]
[9, 3, 4, 5, 2, 7, 6, 0, 8, 1]
[9, 4, 3, 5, 2, 7, 6, 0, 8, 1]
[9, 5, 3, 4, 2, 7, 6, 0, 8, 1]
[9, 7, 3, 4, 2, 5, 6, 0, 8, 1]
[9, 8, 3, 4, 2, 5, 6, 0, 7, 1]
[9, 8, 4, 3, 2, 5, 6, 0, 7, 1]
[9, 8, 5, 3, 2, 4, 6, 0, 7, 1]
[9, 8, 6, 3, 2, 4, 5, 0, 7, 1]
[9, 8, 7, 3, 2, 4, 5, 0, 6, 1]
[9, 8, 7, 4, 2, 3, 5, 0, 6, 1]
[9, 8, 7, 5, 2, 3, 4, 0, 6, 1]
[9, 8, 7, 6, 2, 3, 4, 0, 5, 1]
[9, 8, 7, 6, 3, 2, 4, 0, 5, 1]
[9, 8, 7, 6, 4, 2, 3, 0, 5, 1]
[9, 8, 7, 6, 5, 2, 3, 0, 4, 1]
[9, 8, 7, 6, 5, 3, 2, 0, 4, 1]
[9, 8, 7, 6, 5, 4, 2, 0, 3, 1]
[9, 8, 7, 6, 5, 4, 3, 0, 2, 1]
[9, 8, 7, 6, 5, 4, 3, 2, 0, 1]
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
输入长度: 10 循环次数: 45 比较次数: 45 操作次数: 22

这是从大到小排序的，我们还可以添加一个reverse参数来让函数返回一个从小到大排序的列表。

比如将循环体改成这样

for i in range(length):
    for j in range(i + 1, length):  # 从i + 1开始 减少循环次数
        if data[i] &lt; data[j]:  # 从大到小 如果反了交换
            if reverse: continue
            data[i], data[j] = data[j], data[i]
        elif reverse:  # 如果数据从小到大
            data[i], data[j] = data[j], data[i]</pre>

巧妙地利用了if/else来控制了判断情况。但是效率不佳，因为每次循环都需要进行if的判断，消耗了时间。还不如在结束的时候return data[::-1] if reverse else data ，这样效率还来得高。

¶鸡尾酒排序 Cocktail shaker sort

这其实是一个冒泡排序的改进版本，通过从左到右再从右到左，

def cocktail_shaker_sort(data):
    """Cocktail shaker sort

    使用 ``swapped`` 在必要时候提前结束。

    Args:
        data (List[int]): 待排列表

    Returns:
        List[int]: 有序列表
    """
    length = len(data)

    left, right = 0, length - 1  # 有序序号 左边和右边

    while left &lt; right:
        swapped = False  # 是否一遍过去有没有改变 没有即 已有序
        for i in range(left, right):
            if data[i] &lt; data[i + 1]:  # 与后面一个元素对比
                data[i], data[i + 1] = data[i + 1], data[i]
                swapped = True
        right -= 1
        if not swapped: break
        for i in range(right, left, -1):  # 与前面一个元素对比
            if data[i - 1] &lt; data[i]:
                data[i], data[i - 1] = data[i - 1], data[i]
                swapped = True
        left += 1
        if not swapped: break

    return data

和上面相同的一组数据[3, 5, 4, 8, 2, 7, 6, 0, 9, 1]，可以看到对列表的交换次数没有变化，但循环次数减少了一点，这是因为数据已经提前有序了，程序提前结束了。然而效率却更低了，10000个数据花了13s(12.8131s)，

大的数字一次次地向左走，小的数字一次次地向右走…

调用函数: cocktail_shaker_sort
[5, 3, 4, 8, 2, 7, 6, 0, 9, 1]
[5, 4, 3, 8, 2, 7, 6, 0, 9, 1]
[5, 4, 8, 3, 2, 7, 6, 0, 9, 1]
[5, 4, 8, 3, 7, 2, 6, 0, 9, 1]
[5, 4, 8, 3, 7, 6, 2, 0, 9, 1]
[5, 4, 8, 3, 7, 6, 2, 9, 0, 1]
[5, 4, 8, 3, 7, 6, 2, 9, 1, 0]
[5, 4, 8, 3, 7, 6, 9, 2, 1, 0]
[5, 4, 8, 3, 7, 9, 6, 2, 1, 0]
[5, 4, 8, 3, 9, 7, 6, 2, 1, 0]
[5, 4, 8, 9, 3, 7, 6, 2, 1, 0]
[5, 4, 9, 8, 3, 7, 6, 2, 1, 0]
[5, 9, 4, 8, 3, 7, 6, 2, 1, 0]
[9, 5, 4, 8, 3, 7, 6, 2, 1, 0]
[9, 5, 8, 4, 3, 7, 6, 2, 1, 0]
[9, 5, 8, 4, 7, 3, 6, 2, 1, 0]
[9, 5, 8, 4, 7, 6, 3, 2, 1, 0]
[9, 5, 8, 7, 4, 6, 3, 2, 1, 0]
[9, 8, 5, 7, 4, 6, 3, 2, 1, 0]
[9, 8, 7, 5, 4, 6, 3, 2, 1, 0]
[9, 8, 7, 5, 6, 4, 3, 2, 1, 0]
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
输入长度: 10 循环次数: 42 比较次数: 42 操作次数: 22

可以改进一下让它只是标记最大(最小)的数据的序号而不是直接进行交换来提升效率。

¶选择排序 Selection sort

选择排序也是一种简单直接的排序方式，每一次循环从乱序部分中寻找出最大的那个数字，交换到有序部分的最后去，直到列表都有序。

def selection_sort(data):
    """Selection sort

    Args:
        data (List[int]): 待排列表

    Returns:
        List[int]: 有序列表
    """
    length = len(data)

    for i in range(length):
        index = i  # 最大或最小的序号
        for j in range(i + 1, length):
            if data[j] &gt; data[index]:  # 如果当前值大于循环中最大的记录
                index = j

        # 进行交换
        if index == i: continue  # 如果当前位正确 不必交换
        data[index], data[i] = data[i], data[index]

    return data

在第13行使用了一个index变量来记录当前的位置，用于在第19行与i进行比较避免多余的交换操作。

总共的运行次数和冒泡排序一样，n(n-1)/2次，但是由于交换次数少得多了，速度也就更快了。 10000个数据大概需要6秒(6.2190s) 很明显的提升。

调用函数: selection_sort
[9, 5, 4, 8, 2, 7, 6, 0, 3, 1]
[9, 8, 4, 5, 2, 7, 6, 0, 3, 1]
[9, 8, 7, 5, 2, 4, 6, 0, 3, 1]
[9, 8, 7, 6, 2, 4, 5, 0, 3, 1]
[9, 8, 7, 6, 5, 4, 2, 0, 3, 1]
[9, 8, 7, 6, 5, 4, 3, 0, 2, 1]
[9, 8, 7, 6, 5, 4, 3, 2, 0, 1]
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
输入长度: 10 循环次数: 45 比较次数: 45 操作次数: 8

当然对数组的交换次数小于等于数组个数减一。

¶插入排序 Insertion sort

插入排序也是一种很直接的排序方式，同时也是很低效的一种。

它的思想就是将每一个无序部分的元素插入到有序部分中。在数组元素比较少的时候，用几行就能实现的这个算法看上去很简洁，但一旦数量上去了，每一轮插入需要比较的次数越来越多，拖慢了速度。

插入算法的实现有递归法和迭代法。然而由于递归的方式每一次插入都是一层递归，很快就会触及Python的最大递归层数限制，我们就使用迭代循环的方式。

def insertion_sort(data):
    """Insertion sort

    Args:
        data (List[int]): 无序列表

    Returns:
        List[int]: 有序列表
    """
    length = len(data)  # 输入元素个数

    for i in range(1, length):  # 假设第一个元素已经有序
        now_num = data[i]  # 将要插入的元素
        j = 0  # while循环的指针，指向当前循环中比较的元素的序号

        # 从小到大 如果待排元素大于有序列表中的当前元素 找到该插入的位置
        while data[j] &gt; now_num and j &lt; i:
            j += 1
        if j == i: continue  # 如果当前位正确 不必交换
        data = data[:j] + [now_num] + data[j:i] + data[i + 1:]

    return data

在第20行，利用Python的切片功能将元素插入。不过list自身有list.insert()的方法，也可以实现，两种方法的效率有待对比。

调用函数: insertion_sort
[5, 3, 4, 8, 2, 7, 6, 0, 9, 1]
[5, 4, 3, 8, 2, 7, 6, 0, 9, 1]
[8, 5, 4, 3, 2, 7, 6, 0, 9, 1]
[8, 7, 5, 4, 3, 2, 6, 0, 9, 1]
[8, 7, 6, 5, 4, 3, 2, 0, 9, 1]
[9, 8, 7, 6, 5, 4, 3, 2, 0, 1]
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
输入长度: 10 循环次数: 23 比较次数: 32 操作次数: 7

对于10000个元素，随手测试一下，插入排序的速度甚至比选择排序还要快一些(5.7829s)。

接下来我们可以给这几种常见的 O(n^2) 算法排个序了。通过修改一下之前的count_time我们能够生成一个统计表:

def count_time(func):
    """Timer decorator."""
    @wraps(func)
    def _deco(data, reverse=False, loop_times=1):
        """print running time."""
        result = []  # ordered list
        print("调用函数:", func.__name__)
        time_log = []

        for i in range(loop_times):
            if func.__name__.endswith("reverse"):
                parameter = data[:], reverse
            else:
                parameter = data[:]

            start_time = time.perf_counter()
            result = func(parameter)  # sorting
            end_time = time.perf_counter()

            step_time = end_time - start_time  # lapsed time
            time_log += [step_time]  # add to total time list
            print("{:&lt;20} (第{}次)".format(step_time, i + 1))
        print("{:-&lt;80}\n执行时间: {:&lt;20} (共{}次)".format(
                "", sum(time_log), loop_times))
        print("平均时间: {:&lt;20}\n最好: {}\n最差: {}\n{:=&lt;80}\n".format(
                sum(time_log) / loop_times, min(time_log), max(time_log), ""))

        return result

    return _deco

调用函数	bubble_sort	cocktail_shaker_sort	selection_sort	insertion_sort
第1次	9.51917391	12.35336638	6.022212266	5.317802566
第2次	9.344330736	12.40192877	6.04458919	5.28499465
第3次	9.410286147	12.36908828	6.040824377	5.280491777
第4次	9.420827358	12.39769274	6.04954766	5.267566825
第5次	9.375585338	12.40759763	6.072944658	5.289787123
执行时间	47.07020349	61.9296738	30.23011815	26.44064294
平均时间	9.414040698	12.38593476	6.04602363	5.288128588
最好	9.344330736	12.35336638	6.022212266	5.267566825
最差	9.51917391	12.40759763	6.072944658	5.317802566

可以看出插入 > 选择 > 冒泡 > 鸡尾酒

接下来就是强势的 O(nlog n) 组别了

果果的闪光堆放处

用Python来写各种各样的排序算法 (Part.2)

O(n^2)系列

¶冒泡排序 Bubble sort

¶鸡尾酒排序 Cocktail shaker sort

¶选择排序 Selection sort

¶插入排序 Insertion sort