算法趣解之基础排序算法（上）

之前的文章中提到的二分查找算法中要求数据序列是有序的。然而，生活中的很多数据却是无序的。将无序转换为有序，这就需要排序算法。今天，我们就来一起探索一下几种常见的基础排序算法。

很多基础的排序算法都来源于实际生活中对于某些特定的问题情境的抽象、提炼和总结。你不信？我们一起来分析一下几个例子。

还记得很小的时候，上体育课时，体育老师是如何把你们从高到矮排队吗？老师先目测大家的身高，排出一个基本有序的队伍。然后，依据相邻同学的身高对比，再进行微调。调整的标准如下：

如果相邻两位同学的身高排序不符合当前队伍的高矮要求，那么交换这两个同学的位置；否则，不做调整。

将队伍中相邻的同学都做如上所述的调整，那么同学们就可以排成一个有序的队伍了。

这种排序方法的关键点，我相信大家可以很容易发现，即：比较相邻的两个数据，若顺序不对，则将其位置交换。

那么这种方法如何交由计算机来实现呢？在从实际方法到计算机实现的过程中，我们经常会遇到一个困难，即，在具体情境下的处理流程不能直接拿来就用。这就需要我们做一定的转化。比如本例，老师可以先目测，排出基本有序的队伍，而计算机不会目测。如何解决这个问题呢？利用计算机可以机械地、重复地处理一些基本运算的特性，我们将每一种相邻的情况枚举出来，再判断处理，就可以实现这个排序方法。

有关这种排序方法的处理流程，我们通过一个具体的数字排序例子来感受一下。

比如有一个无序数字序列如下：

我们要使用上述的排序方法，使之从小到大排列。

我们从头开始对数据进行对比处理。

①对比第1个和第2个数据，第2个数据较小，因而需要交换。交换后的序列如下

②对比第2个和第3个数据，两个数据排列符合排序要求，因而不需要交换。此次处理后的序列如下：

③同样的方式处理，可以得到以下序列

（P.S.87和88比较，顺序符合要求，不交换）

（P.S.88和61比较，不符合顺序要求，交换）

经过这一轮的排序，我们发现序列中的最大值已经达到目标位置，但是整个序列还不是有序的。如何解决呢？可以仿照这一轮的排序对之前无序的序列做同样的操作。

第二轮的排序每次的序列如下所示：

（P.S.83和84比较，顺序符合要求，不交换）

（P.S.84和87比较，顺序符合要求，不交换）

（P.S.87和61比较，不符合顺序要求，交换）

经过这一轮的排序，次大值也到了目标位置。

第三轮：

（P.S.83和84比较，顺序符合要求，不交换）

（P.S.84和61比较，不符合顺序要求，交换）

第四轮

（P.S.83和61比较，不符合顺序要求，交换）

通过上面这个实际的例子，我们发现，每一轮排序都会在前面无序的序列中通过交换相邻数字的方式找到其中的最大值，和后面的数字形成一个有序的部分。这个过程就像水中的一个气泡，从底端慢慢的飘升到水面的过程，所以我们将这种排序算法成为“冒泡排序”。

到了实现环节，就需要选择合适的存储结构，并利用三种基本的程序结构来描述这个算法的流程。

由于排序过程中涉及到交换，链表中的数据位置交换比较复杂，为了简单起见，我们利用数组来实现。算法流程中的很多次的比较可以通过循环加上分支来描述。

因而，有如下的Python代码：

def bubble_sort(lst):
    """
    冒泡排序：
      将一个无序的数据列表lst转换为从小到大的返回
     参数：
      lst：待排序的数据列表
     返回：
      排好序的数据列表
    """
    for i in range(len(lst)):                          #排序轮数
        for j in range(len(lst) - i - 1):              #每一轮的排序次数
            if lst[j] > lst[j+1]:
                lst[j],lst[j+1] = lst[j+1],lst[j]      #这里交换相邻的数据，用到了python中的特殊写法。具体可以百度"python a,b=b,a"
            print("第{}轮第{}次排序后结果：".format(i+1, j+1))
            print(lst)
            print()                                    #打印空行
    return lst

lst = [84, 83, 88, 87, 61]

print("调用函数:",bubble_sort(lst))
"""
第1轮第1次排序后结果：
[83, 84, 88, 87, 61]

第1轮第2次排序后结果：
[83, 84, 88, 87, 61]

第1轮第3次排序后结果：
[83, 84, 87, 88, 61]

第1轮第4次排序后结果：
[83, 84, 87, 61, 88]

第2轮第1次排序后结果：
[83, 84, 87, 61, 88]

第2轮第2次排序后结果：
[83, 84, 87, 61, 88]

第2轮第3次排序后结果：
[83, 84, 61, 87, 88]

第3轮第1次排序后结果：
[83, 84, 61, 87, 88]

第3轮第2次排序后结果：
[83, 61, 84, 87, 88]

第4轮第1次排序后结果：
[61, 83, 84, 87, 88]

调用函数: [61, 83, 84, 87, 88]
"""

最后，我们简单地评价一下这个算法的性能。在上面一个具体的算法流程中，我们可以发现如下的规律：

对于一个含有 \(N\) 个数据元素的序列，它需要进行 \(N – 1\) 轮比较，每一轮（记轮数为 \(i\) ，从1开始计数）比较中又需要比较 \(N – i\) 次比较。所以，一个完整的“冒泡排序”过程总共需要

\[ \begin{aligned} &\ \ \ \ \ ( N - 1 ) + ( N - 2 ) + ··· + 1\\ &=\frac{( N - 1 )( N - 1 + 1 )}{2}\\ &= \frac{N(N - 1)}{2} \end{aligned} \]

次比较。所以“冒泡排序”算法的时间复杂度为 \(O(N^{2})\) 。

好了，今天就到这里。让我们简单回顾一下本文的要点：

冒泡排序算法的核心思想：比较相邻的两个数据，若顺序不对，则将其位置交换。
冒泡排序的时间复杂度为 \(O ( N^{2} )\) 。