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] < 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] < 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 < right:
        swapped = False  # 是否一遍过去有没有改变 没有即 已有序
        for i in range(left, right):
            if data[i] < 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] < 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] > 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] > now_num and j < 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("{:<20} (第{}次)".format(step_time, i + 1))
        print("{:-<80}\n执行时间: {:<20} (共{}次)".format(
                "", sum(time_log), loop_times))
        print("平均时间: {:<20}\n最好: {}\n最差: {}\n{:=<80}\n".format(
                sum(time_log) / loop_times, min(time_log), max(time_log), ""))

        return result

    return _deco

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