Python 排序算法[一]：令你茅塞顿开，却又匪夷所思

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。

算法的几大特征

一个算法应该具有 “有穷性”、“确切性”、“输入项”、“输出项”、“可行性” 等重要的特征。这些特征对应的含义如下：

• 有穷性（Finiteness）-- 算法的有穷性是指算法必须能在执行有限个步骤之后终止；
• 确切性 (Definiteness) -- 算法的每一步骤必须有确切的定义；
• 输入项 (Input) -- 一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
• 输出项 (Output) -- 一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
• 可行性 (Effectiveness) -- 算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。

算法两大要素

• 一，数据对象的运算和操作：计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，成为该计算机系统的指令系统。一个计算机的基本运算和操作有如下四类：

  • 1 算术运算：加减乘除等运算
  • 2 逻辑运算：或、且、非等运算
  • 3 关系运算：大于、小于、等于、不等于等运算
  • 4 数据传输：输入、输出、赋值等运算 [1]

• 二，算法的控制结构：一个算法的功能结构不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。

算法的好坏评定

你说这个算法好、他却说这个算法不好，两人争论不休。那么好与不好应该怎么评定呢？

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

• 时间复杂度 -- 算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做。 T(n)=Ο(f(n)) 因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。
• 空间复杂度 -- 算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。
• 正确性 - 算法的正确性是评价一个算法优劣的最重要的标准。
• 可读性 - 算法的可读性是指一个算法可供人们阅读的容易程度。
• 健壮性 - 健壮性是指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性。

以上的理论知识可以让我们对算法有个大致的理解和认知，接下来我们将使用 Python 实现几个经典的 排序算法 ，并在文末对比 Java 的实现。

算法的内外之分

除了《唐门》弟子之外（斗罗大陆中的唐门），排序算法也有内外之分。

• 内部 排序 指的是在内存中进行排序；
• 外部排序指的是由于数据量较大，无法读入内存而需要在排序过程中访问外部存储的情况；

比较经典的 排序算法 如下图所示：

有冒泡排序、归并排序、插入排序、希尔排序、选择排序、快速排序等。

它们各自的时间复杂度如下图所示：

注意：今天先讲冒泡、选择和插入排序

在开始之前，首先要感谢公众号《五分钟学算法》的大佬 “程序员小吴” 授权动态图片和排序思路。

冒泡排序

冒泡排序的过程如上图所示，对应的算法步骤为：

根据动态图和算法步骤， Python 实现冒泡排序的代码如下：

data = [5, 4, 8, 3, 2]
def bubble(data):
    for i in range(len(data)-1):    # 排序次数
        for s in range(len(data)-i-1):  # s为列表下标
            if data[s] > data[s+1]:
                data[s], data[s+1] = data[s+1], data[s]
    return data
print(bubble(data))
复制代码

程序运行后输出结果为:

[2, 3, 4, 5, 8]
复制代码

这是一种时间复杂度上限比较高的方法，它的排序时间会随着列表长度的增加而增加。

选择排序

选择排序的过程和步骤如上图所示，根据动态图和算法步骤， Python 实现选择排序的代码如下：

data = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
def selections(nums):
    for i in range(len(nums)):
        min_index = min(nums)  # 最小值
        for j in range(len(nums) - i):
            if nums[min_index] < nums[j]:
                min_index = j
        nums[min_index], nums[len(nums) - i - 1] = nums[len(nums) - i - 1], nums[min_index]
    return nums
print(selections(data))
复制代码

其中 min() 方法可以获得列表中的最小值，运行结果为：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
复制代码

既然 min() 有这个特性 (备注：max() 方法可以获得列表中最大值)，我们可以将它利用起来，骚一点的代码为：

data = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
res = []
for i in range(0, len(data)):
    aps = min(data)
    data.remove(aps)
    res.append(aps)
print(res)

复制代码

运行后得到的输出结果为：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
复制代码

假如将 min() 换成 max() 方法的，得到的输出结果为：

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
复制代码

这种只选择列表最大元素或最小元素的行为，是否也能称为选择性排序呢？

虽然这种写法的代码比较短，也更容易理解。但是它的时间复杂度是如何的呢？

首先要确认 min 和 max 的时间复杂度。有人给出了 list 各项操作的时间复杂度：

可以看到 min 和 max 都是随着列表长度而增长，再加上本身需要 for 循环一次，所以这种写法的时间复杂度为

真的是这样吗？

代码中有一个 remove 操作，将原列表的元素删除，但是 remove 的时间复杂度也是O(n)，这岂不是变成了 O(n*n + n)，如何解决这个问题呢。

观察到 pop 的时间复杂度是 O(1)，那么是否可以利用 pop 来降低时间复杂度呢？list 提供了获取元素下标的方法，我们尝试将代码改为：

data = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
res = []
for i in range(0, len(data)):
    aps = max(data)
    result = data.pop(data.index(aps))
    print(result)
    res.append(aps)
print(res)
复制代码

运行后得到的输出结果为：

9
8
7
6
5
4
3
2
1
0
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
复制代码

由此可见确实能够根据索引删除掉 list 元素，在删除元素这里降低了复杂度。

慢着，上述 pop 的时间复杂度是 O(1)，但是 pop(data.index(i)) 这种操作的时间复杂度呢？也是 O(1) 吗？我们可以做个实验来验证一下：

# 崔庆才丨静觅、韦世东丨奎因 邀请你关注微信公众号【进击的Coder】
from datetime import datetime
data = [i for i in range(500000)]

start_time = datetime.now()
for i in range(len(data)):
    data.pop(data.index(i))
print(data)
print(datetime.now() - start_time)
复制代码

这是 pop(data.index(i)) 的代码，运行结果如下：

[]
0:00:40.151812
复制代码

而如果使用 pop()

from datetime import datetime
data = [i for i in range(500000)]

start_time = datetime.now()
for i in range(len(data)):
    data.pop()
print(data)
print(datetime.now() - start_time)

复制代码

运行后的结果为：

[]
0:00:00.071441
复制代码

结果显而易见，pop(i) 的时间复杂度依旧是跟元素个数有关，而不是预想中的 O(1)。由于列表元素不断减少，所以它的时间复杂度也不是 O(n)，假设当前列表元素数量为 k，那么这个部分的时间复杂度则是 O(k)。说明简短的 min max写法能够一定程度的降低时间复杂度。

验证一下，两次 for 循环的选择排序写法和 mix max 的简短写法耗时情况如何：

from datetime import datetime
data = [i for i in range(30000)]


def selections(nums):
    for i in range(len(nums)):
        min_index = min(nums)  # 最小值
        for j in range(len(nums) - i):
            if nums[min_index] < nums[j]:
                min_index = j
        nums[min_index], nums[len(nums) - i - 1] = nums[len(nums) - i - 1], nums[min_index]
    return nums


start_time = datetime.now()
selections(data)
print(datetime.now() - start_time)
复制代码

这里以 3 万个元素为例，两次 for 循环的运行时间为 47 秒左右。而同样的数量，用 min max 方式排序：

from datetime import datetime
data = [i for i in range(30000)]

start_time = datetime.now()
res = []
for i in range(0, len(data)):
    aps = max(data)
    # del data[data.index(aps)]
    data.pop(data.index(aps))
    res.append(aps)
print(datetime.now() - start_time)
复制代码

所花费的时间为 12 秒，代码中用 del 和 pop 方法得到的结果一样。

还……还有这种操作？

选择排序也是一种时间复杂度上限比较高的方法，它的排序时间同样会随着列表长度的增加而增加。

插入排序

插入排序的过程和步骤如上图所示，根据动态图和算法步骤， Python 实现插入排序的代码如下：

from datetime import datetime
data = [i for i in range(30000)]
data.insert(60, 5)

# 崔庆才丨静觅、韦世东丨奎因 邀请你关注微信公众号【进击的Coder】
def direct_insert(nums):
    for i in range(1, len(nums)):
        temp = nums[i]  # temp变量指向尚未排好序元素（从第二个开始）
        j = i-1  # j指向前一个元素的下标
        while j >= 0 and temp < nums[j]:
            # temp与前一个元素比较，若temp较小则前一元素后移，j自减，继续比较
            nums[j+1] = nums[j]
            j = j-1
            nums[j+1] = temp  # temp所指向元素的最终位置
    return nums


start_time = datetime.now()
res = direct_insert(data)
print(datetime.now() - start_time)
print(len(res), res[:10])
复制代码

生成列表后在列索引为 60 的地方插入一个值为 5 的元素，现在数据量为 3 万零 1。代码运行得到的输出结果为：

0:00:00.007398
30001 [0, 1, 2, 3, 4, 5, 5, 6, 7, 8]
复制代码

可以看到 3 万零 1 个元素的列表排序耗时很短，而且通过切片可以看到顺序已经经过排列。

然后测试一下选择，代码如下：

from datetime import datetime
data = [i for i in range(30000)]
data.insert(60, 5)


def selections(nums):
    for i in range(len(nums)):
        min_index = min(nums)  # 最小值
        for j in range(len(nums) - i):
            if nums[min_index] < nums[j]:
                min_index = j
        nums[min_index], nums[len(nums) - i - 1] = nums[len(nums) - i - 1], nums[min_index]
    return nums


start_time = datetime.now()
res = selections(data)
print(datetime.now() - start_time)
print(len(res), res[:10])
复制代码

代码运行后得到的输出结果为：

0:00:47.895237
30001 [0, 1, 2, 3, 4, 5, 5, 6, 7, 8]

复制代码

可以看到 3 万零 1 个元素的列表排序耗并不短，耗费了 47 秒钟，通过切片可以看到顺序已经经过排列。

接着试一下 max min 型选择排序的写法，得到的结果为：

0:00:14.150992
30001 [29999, 29998, 29997, 29996, 29995, 29994, 29993, 29992, 29991, 29990]
复制代码

这简直了，为什么这种操作就能够节省这么多时间呢？

最后测试一下冒泡：

# 崔庆才丨静觅、韦世东丨奎因 邀请你关注微信公众号【进击的Coder】
from datetime import datetime
data = [i for i in range(30000)]
data.insert(60, 5)


def bubble(data):
    for i in range(len(data)-1):    # 排序次数
        for s in range(len(data)-i-1):  # s为列表下标
            if data[s] > data[s+1]:
                data[s], data[s+1] = data[s+1], data[s]
    return data


start_time = datetime.now()
res = bubble(data)
print(datetime.now() - start_time)
print(len(res), res[:10])

复制代码

代码运行后得到的输出结果为：

0:00:41.392303
30001 [0, 1, 2, 3, 4, 5, 5, 6, 7, 8]
复制代码

可以看到 3 万零 1 个元素的列表排序耗并不短，耗费了 41 秒钟，通过切片可以看到顺序已经经过排列。

得到的结果为：

• 冒泡排序 - 41
• 选择排序（两层 for） - 47
• 选择排序（max mix） - 14
• 插入排序 - 0.007398

问题：实在是令人匪夷所思，插入排序的速度居然比其他两种排序方式耗时少那么多。这是为什么呢？

事实上插入排序只用了 1 层 for 循环，并非像冒泡和选择那样使用 2 层 for 循环，是不是由此可以刷新上图中对于时间复杂度的介绍呢？

问题：而两种不同的选择排序法的结果差异这么大，这又是为什么？？？

请在评论区发表你的看法