排序算法，就是使得记录按照要求的顺序排列的方法，即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。这种新序列遵循着一定的规则，体现出一定的规律，因此，经处理后的数据便于筛选和计算，大大提高了计算效率。

　　排序算法在很多领域得到重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。要得到一个符合实际的优秀算法，往往需要经过大量的推理和分析。

　　一般来说排序有升序排列和降序排列两种方式，常用的排序算法包括：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序。

　　其中堆排序在第三十八课中已介绍过，后面对其他排序算法做细致讲解。10种常见排序算法可以分为以下两大类。

　　(1)比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlgn)，因此也称为非线性时间比较类排序。比较类排序包括冒泡排序，选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序。

　　(2)非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较类排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。非比较类排序包括计数排序、桶排序和基数排序。

　　要研究排序优劣，不能武断，那么就需要一些有关排序的指标。排序的三个主要指标是稳定性/不稳定性、时间复杂度和空间复杂度。

　　稳定性/不稳定性

　　所谓稳定性是指待排序的序列中有两个或多个元素的比较数值相等，排序之后它们的相对先后顺序不变则为稳定排序；如果相等元素的相对位置有可能因为排序而发生改变，则此排序为不稳定排序。假如数列中两个元素为A1、A2，它们的索引（数组或列表下标）位置subIndex_A1>subIndex_A2，如果排序之后虽然A1、A2的索引位置可能变化了，但仍然保证新的索引位置new_subIndex_A1>new_subIndex_A2，则为稳定，否则为不稳定。

　　为什么要强调稳定性/不稳定性呢？举个例子，假如有一个打疫苗的排队系统的逻辑是：老弱病残孕妇优先，每次有人要出队时先把所有排队的人顺序打乱，然后按类别排队。

　　程序代码（文本代码附录１）：

　　运行结果：

　　从结果上看，这个奇葩排队系统真“不稳定”，一定会制造混乱。

　　如果待排序数组中元素是单纯数字，排序后元素的前后顺序发生变化并没有什么关系，但如果是其他的格式（比如上例中排队的人），那不稳定那就有很大问题。

　　时间复杂度

　　时间复杂度不是一个数值，而是一种数量趋势的模式。在数学上表示数量趋势的模式的常用方法之一就是函数。也就是说排序算法的时间复杂度是一个函数。我们知道一个一元函数由一个自变量（x）和一个因变量（y）构成（y=f(x)）。对于排序，自变量当然是数据的个数n，关键是什么是因变量（函数值）呢？

　　对于一段代码，字符数多少、行数等与运行时间没有什么直接的关系。为能有一个与时间有关系的东西，首先选定代码中一些语句作为标的语句，然后代码整个运行过程执行这些语句的次数作为因变量。次数少，用时少；次数多用时多，确实与运行时间有关。因为实际的运行时间还与运行的环境有关，所以它只是定性描述运行时间而已，确切来说是运行频度。

　　那么，代码的总运行频度法f和数据的个数n的函数（不妨叫做频度函数）能否作为时间复杂度呢？我们先看下面两段代码的这种函数（忽略 for 那一行）。

代码１：

1　n=10

2　for i in range(n):

3　　　print("Hello,World")

第一行只运行一次，运行频度=１，第三行运行n次，运行频度=n，那么总运行频度=n+1，即频度函数：f = n + 1。

代码２：

1　n=10

2　for i in range(n):

3　　　print("Hello,World")

4　print("Hello,World")

第一行只运行一次，运行频度=１，第三行运行n次，运行频度=n，第四行只运行一次，运行频度=１，那么总运行频度=n+2，即频度函数：f = n + 2。

　　可见，代码稍有不同，频度函数就不一样了，不可以作为比较的指标，因此是不可以作为时间复杂度的。那么应该用什么呢？对于下面三个函数

f = n，

f = n + 1，

f = n + 2，

当n很大时，n : (n + 1) : (n + 2) ≈ 1 : 1 : 1。也就是说n+1和n+2都趋向n，f = n函数就是它们的时间复杂度。

　　时间复杂度常用大O符号表示，跟着的小括号是函数体（即函数等号右侧）。那上面两段代码的时间复杂度是O(n)。如果通过频度函数来推导出时间复杂度呢？

　　时间复杂度不是定量的指标，它是定性的指标，因此不能用正常的数量推导方法。为此我们定义"复杂度单项式"：

　　（１）用乘法分配率去括号后，最外层运算符没有加减号的代数式。例如，因为n*(n+1)=n*n + n，所以n*(n+1)不是复杂度单项式。

　　（２）忽略复杂度单项式的常数系数，例如，2n²转化为复杂度单项式是n²。

　　（３）两个复杂度单项式的比值，在所有自变量是无穷大时，如果比值也是无穷大，那么第一个复杂度单项式的阶次比第二个高（例如，n²/n=n）；如果比值是无穷小，那么第一个比第二个低（例如，n/n²=1/n）；如果等于１，阶次相等（例如n²/n²=1）。

　　（４）一个高阶的一元复杂度单项式与有限个数的低阶同元复杂度单项式的和或差，结果还是原来的一元复杂度单项式（例如n²+1=n²，n²+n+1=n²）。

　　（５）不同元的两个复杂度单项式无法比较阶次高低，因此是不能合并的。

　　把一个时间频度函数右侧代数式，通过上面的方法转化为复杂度单项式（一元）或多个复杂度单项式之和（多元）的函数，就可以作为时间复杂度了。

　　先看下面的嵌套循环代码：

1　n = 10

2　sum=0

3　for i in range(n):

4　　for j in range(n):

5　　　sum += 1

时间频度=1+1+n*n*1=2+n²，由第（３）、（４） 条，可知时间复杂度是O(n²)。

　　再看下面的嵌套循环代码：

1　n = 10

2　m = 20

3　sum=0

4　for i in range(n):

5　　for j in range(m):

6　　　tp = 1

7　　　sum += tp

时间频度=1+1+1+n*m*(1+1)=3+2n*m，由第（２）、（３）、（４） 条，可知时间复杂度是O(n*m)。可见一段代码里只有一个两层的嵌套循环，它的时间复杂度都是O(n*m)，并不是真正的时间频度，确实是“定性”的。

　　再看下面的循环代码：

1　n= 100

2　i = 1

3　while i<=n:

4　　i = i * 2

上面的循环次数不能直接得出，因此设循环次数是x，那么这时i = 1 * 2^x，得2^x=n，所以x是n的以2为底的对数（x  = log2n）。时间频度= 1+1+log2n，当n是无穷大时，log2n也是无穷大，所以时间复杂度是O(log2n)。

　　排序的空间复杂度

　　一个程序的空间复杂度是指运行完一个程序所需内存的大小，这部分内存占用分为如下两部分：

　　(1)固定空间：其空间大小与输入/输出的数据的个数多少、数值无关，主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间，这部分属于静态空间。比如：

　　指令空间：执行一段算法，20行代码就比10行代码多消耗一倍的指令空间。

　　数据空间：一段算法中，定义了一个int类型，就会在内存中开辟4字节的空间。

　　(2)可变空间：其空间主要包括动态分配的空间以及递归栈所需的空间等，这部分的空间大小与算法有关。比如：

　　一个算法中定义了一个函数，当这个函数被执行到调用时，函数会被压栈操作，栈中会为这个函数开辟空间，函数执行完毕，函数会被弹栈，栈中的这部分空间会被收回。假设有一个数组ar=[1,2,3,4,5]，是一个int型的数组，在内存中，每个元素占4字节的空间，这个数组共5个元素，于是固定部分内存占用为4×5=20字节，如果用冒泡排序或插人排序，数值只在数组内移动，除了固定空间部分外，将不再另外开辟新的空间。

　　如果用链表排序，每个链表节点包含一个数值和一个指向下一个节点的指针，每个指针占4字节，于是一个元素就占8字节，整个链表中的全部元素在内存中就占8人5=40字节。

　　如果用二叉树排序，每个二叉树节点包含一个数值、一个左指针和一个右指针，每个节点占静态空间共12字节，整个树结构在内存中就占12×5=60字节。

　　一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为递归算法，其空间复杂度为递归所使用的堆栈空间的大小，它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1，这个1表示开始进行的一次非递归调用)。

　　算法的空间复杂度一般也以类似时间复杂度的形式给出。如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)；当一个算法的空间复杂度与n成线性比例关系时，可表示为O(n)。

　　若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。

　　时间复杂度和空间复杂度只是定性的，是渐进的复杂度（规模较大时的复杂度），所以排序代码的模式就有确定的复杂度。也就是说，我们只需理解复杂度的概念，知道各种代码模式的复杂度，就可能推算出具体代码的复杂度。

　　排序的时间复杂度除了与代码模式有关，也与待排序的数据的初始状态有关。例如，已排好序的数组[0,1,2,3,4,5,6,7,8,9]排序，只需从头到尾检查一次就行了，即时间复杂度（最好）是O(n)；如果是倒序的[9,8,7,6,5,4,3,2,1,0]的，那检查的次数是n(n+1)/2次，即时间复杂度（最坏）是O(n²)；最好与最坏之间就有一个平均的时间复杂度。由于时间复杂度本身是定性的，因此是不可以通过最好和最坏的时间复杂度去求平均时间复杂度，而是通过统计数学得到平均频度函数，再由平均频度函数的渐进方式而确定。

　　10种常见排序算法的复杂度

　　下表是10种常见的排序算法在时间复杂度和空间复杂度的平均、最好、最坏情况下以及它们的稳定性的对比。这十种排序算法会在后续的课中讲述。

　　学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：

Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。

更多课程请打开“学思营”同步网站：

http://www.5xstar.com/doc.html

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社

附录１：

#稳定/不稳定的排队系统
import random as r  #导入随机模块并重命名为r
VIP, NORMAL = 0, 1  #排队人的类别
lst = [(r.choice([VIP, NORMAL]), i) for i in range(1,10)]  #生成9个人的队列
mlst = sorted(lst, key=lambda p : p[0])  #用内置函数排队
print("sorted排队前后对比（稳定的）：")
print(lst)
print(mlst)
nlst = [] #新队列收集表
while len(nlst) < len(lst):
    p = r.choice(lst)  #抽取1人
    if len(nlst) == 0:  #第一个人
        nlst.append(p) #加入后继续抽取
        continue
    for old in nlst:
        if old[1] == p[1]:  #该人已抽过，继续抽取
            break
    else:  #未抽过
        if p[0] == VIP:  #如果是VIP插在队列前面，否则放最后
            nlst = [p] + nlst
        else:
            nlst.append(p)
print("奇葩排队前后对比（不稳定的）：")
print(lst)
print(nlst)