冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

原理

比较相邻的元素，如果第一个比第二个大，就交换。对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

时间复杂度

冒泡算法每次都需要对元素进行比较，是一种稳定的排序算法，时间复杂度为：O（n²）

Python实现

# -*- coding:utf-8 -*-
# 冒泡排序

'''
重点：每一轮比较都把最大的数放到最后，第二层循环的循环次数是递减的，
所以j终止的条件是 j = end - i - 1
'''

# while 写法
def bubble_sort(list):
    # if len(list) < 1:
    #     return list

    i = 0
    end = len(list) - 1
    while i < end:
        j = 0
        while j < end - i:
            if list[j] > list[j + 1]:
                list[j], list[j + 1] = list[j + 1], list[j]
            j = j + 1

        i = i + 1

    return list

# for 写法
def bubble_sort_for(list):
    # if len(list) < 1:
    #     return list

    end = len(list)

    # 外循环次数等于需排序个数减 1，比如3个数字，只需要循环两轮，i初始为0
    for i in range(end - 1):
        for j in range(end - i - 1): # 单趟排序比较的次数要减去已排序好的个数（即 i）
            if list[j] > list[j + 1]:
                list[j], list[j + 1] = list[j + 1], list[j]
    return list

参考上一篇文章：Redis配合ThinkPHP（tp6.0.8）实现消息队列

配置

和Redis版本不一样地方主要在于config\queue.php配置，如下图：

和Redis版本一样，配置文件中其他参数都是安装think-queue时默认生成的，我没有做改动。

重点部分

和Redis不同的是，MySQL实现消息队列需要两个数据库表：jobs和failed_jobs（如果是自己添加时需加上前缀），通过migrate方式生成，会自动添加表前缀。

首先，安装think-queque扩展：composer require topthink/think-migration，如果是tp5.1，则只能安装2.x版本，使用命令：composer require topthink/think-migration=2.0.*。

然后，执行两条命令，分别生成jobs和failed_jobs表的迁移类文件：
php think queue:table
php think queue:failed-table

最后，执行php think migrate:run，数据库表就生成好了。

当然，也可以自行在数据库中添加这两张表，下面列出它们的结构：

CREATE TABLE `jobs` (
 `id` int(11) NOT NULL AUTO_INCREMENT,
 `queue` varchar(255) NOT NULL,
 `payload` longtext NOT NULL,
 `attempts` tinyint(3) unsigned NOT NULL,
 `reserve_time` int(11) unsigned DEFAULT NULL,
 `available_time` int(11) unsigned NOT NULL,
 `create_time` int(11) unsigned NOT NULL,
 PRIMARY KEY (`id`),
 KEY `queue` (`queue`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8

CREATE TABLE `failed_jobs` (
 `id` int(11) NOT NULL AUTO_INCREMENT,
 `connection` text NOT NULL,
 `queue` text NOT NULL,
 `payload` longtext NOT NULL,
 `exception` longtext NOT NULL,
 `fail_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
 PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8

剩余的操作和Redis一致，全文结束。

运行环境

Windows 10 本地环境
PHP 7.2.9
ThinkPHP v6.0.8
Redis v3.2.100

安装

tp6.0只能通过composer方式安装，而且默认框架不带ORM和Queue，都需要通过composer方式安装。tp6.0环境默认安装的是最新版think-queue，目前是3.X版本。
composer require topthink/think-queue

注意：如果是tp5.1，只能安装2.X版本，命令为：composer require topthink/think-queue=2.*

验证是否安装成功，只需命令行执行：php think queue:listen -h，看到如下画面，说明安装成功。

配置

安装成功之后，在config目录下会有一个queue.php文件，我们选择redis驱动类型，默认驱动类型是sync，即同步执行。

- 阅读剩余部分 -

原理

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
这是一种递归算法，每次将一个列表一分为二，如果列表为空或只有一个元素，那么从定义上来说它就是有序的。如果列表不止一个元素，就将列表一分为二，并对两部分都递归调用归并排序。
该算法1945年由约翰·冯·诺伊曼首次提出。

时间复杂度

归并排序是一种稳定的排序算法，时间复杂度为：O(nlogn)

# -*- coding:utf-8 -*-
# 归并排序

def mergeSort(alist):
    if len(alist) > 1:
        mid = len(alist) // 2 # 向下取整
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        lefthalf = mergeSort(lefthalf)
        righthalf = mergeSort(righthalf)

        i = 0
        j = 0
        k = 0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k] = lefthalf[i]
                i = i + 1
            else:
                alist[k] = righthalf[j]
                j = j + 1
            k = k + 1

        while i < len(lefthalf):
            alist[k] = lefthalf[i]
            i = i + 1
            k = k + 1

        while j < len(righthalf):
            alist[k] = righthalf[j]
            j = j + 1
            k = k + 1
    return alist

b = [54, 26, 93, 17, 77, 31, 44, 55, 20]
mergeSort(b)

原理

在列表较低的一端维护一个有序的子列表，并逐个将后面每个新元素“插入”这个子列表。

1. 将待排序列表的第一个元素当做已排序序列，第二个元素到最后一个元素当成未排序序列。
2. 取未排序序列中的第一个数据，插入到已排序序列中顺序正确的位置。将未排序的第一个数据与相邻的前一个数据(已排序序列的最后一个数)据进行比较，如果顺序错误则交换位置，交换位置后继续与相邻的前一个数据进行比较，直到不需要交换则插入完成。每次插入数据后，已排序序列都是排好序的。
3. 重复上一步，继续插入下一个数据。每进行一次插入，已排序序列的长度加1，未排序序列的长度减1，直到列表中的所有数据都插入到已排序序列了，则列表排序完成。

时间复杂度

插入排序的时间复杂度也是O(n²)。

Python 实现

# -*- coding: UTF-8 -*-
# 插入排序

def insertionSort(alist):
    for index in range(1, len(alist)):
        currentvalue = alist[index]
        position = index

        while position > 0 and alist[position-1] > currentvalue:
            alist[position] = alist[position-1]
            position = position-1

        alist[position] = currentvalue
    return alist