第5课排序算法（一）¶

排序问题是计算机中非常经典的一个问题。在今天的所有计算机程序中，绝大部分都需要进行应用到数据的排序算法。并且排序算法难度适中，所以排序算法成为算法学习中非常重要的一部分。

排序算法发展到现在已经有非常多种，各有各不同的特点和性能。本节课我们将挑出三种比较容易理解的算法，先来初步感受排序算法。

要注意在下面的排序算法中，除非有特别说明，否则排序都指升序排列。

冒泡排序算法（Bubble Sort）¶

冒泡算法的名字来源于在排序时数字会像“泡泡“一样由底部移动到头部这一过程。冒泡排序的步骤非常简单，一句话可以进行概括：将相邻的两个数字进行比较，如果前一个数字大于后一个数字，则将他们进行交换；不停重复以上步骤直到数列变得有序。

请大家看下面的动画，以了解冒泡排序的过程：

bubble_sort

算法思路¶

首先我们来看一次冒泡的过程： 1. 初始化设置当前位置j为数组第0个元素。 2. 将当前位置j对应的数值与其后一个(j+1)数值进行比较，如果位置错误(非升序）则进行交换。 3. 将当前位置j移动到下一个位置，然后进行步骤1，直到到达数组倒数第二个位置len(nums) - 2。

在上面动图例子中，当第一次排序完成后，最后整个数列的情况如下所示：

可以看到，这一轮交换操作的后，把这串数字中最大的数字进行正常归位了，放到了最后的位置。接下来我们可以使用同样的操作，将前半部分的数组进行正确的归位。

代码实现¶

def buble_sort(nums: List[int]):
    for i in range(len(nums) - 1):
        # 特别注意此处的结尾条件
        for j in range(len(nums) - 1 - i):
            if nums[j] > nums[j+1]:
                temp = nums[j]
                nums[j] = nums[j+1]
                nums[j+1] = temp

性能分析¶

时间复杂度¶

当进行排序算法时，遇到的最坏情况是什么呢？那就是数列在最初阶段就是按降序排列的，此时，我们需要进行最多次的比较和交换的操作。在这种情况下：若当前的数组长度为 $n$ ，则第一次“冒泡”时，需要 $n - 1$ 次交换操作，第2次“冒泡”时需要进行 $n - 2$ 次冒泡操作…… 最后可以得到最坏情况下的总比较次数：

\sum_{i = 1}^{n - 1} i = \frac{1}{2} n^{2} - n

所以可以得到最坏情况下的复杂度为 $O (n^{2})$ 。

平均算法复杂度的计算比较麻烦，这里不再详细展开，不过可以肯定的是，冒泡平均时间复杂度也为 $O (n^{2})$ 。

小伙伴请思考，那最好情况是什么？

空间复杂度¶

在冒泡排序算法中，仅仅使用了一个用于交换两数的临时变量，所以所需内存空间与数组长度无关，所以空间复杂度为 $O (1)$ 。

选择排序算法（Selection Sort）¶

选择排序算法是另一种更直观的方法，他的思路也很简单：扫描数组，选择最小值放到第0位，紧接着继续遍例1至 n-1的子数组，选择最小值放到第1位，以此反复，最终使数组变得有序。

请看以下的动画示例：

selection

算法思路¶

插入排序算法的思路比较简单，比较符合人的正常思维的做法。但是具体到编程语言实现上要注意几点：

当选择出数组中最小值时，将其放到数组的开头处，但是要注意数组开头的数字不要被覆盖了，你可以直接交换这两个值。
在遍例数组时，需要记录最小值和最小值所在的索引，才能进行交换。
过程中，会在数组中形成两个区域，一个是有序区，剩下的部分是待排序区。

有了以上几点，可以来看看下面的Python语言实现。

代码实现¶

def selection_sort(nums: List[int]):
    for i in range(0, len(nums)):
        min_num = nums[i]
        min_index = i
        for j in range(i, len(nums)):
            # 找到未排序区最小的数字，记录其位置
            if nums[j] < min_num:
                min_num = nums[j]
                min_index = j

        # 将未排序区的数字放到正确位置
        temp = nums[i]
        nums[i] = nums[min_index]
        nums[min_index] = temp

算法性能分析¶

时间复杂度¶

请小伙伴们推导一下选择排序的时间复杂度是多少？最坏情况是什么时候？

空间复杂度¶

与冒泡排序相同，选择排序的空间复杂度是 $O (1)$

插入排序算法¶

插入排序算法在生活中我们也经常遇到。比如在打扑克牌的时候，面对一手乱序的牌，人们会自然的使用类似插入排序算法。其基本原理可以简单描述：将每一个数字与前面的数字比较，在合适位置时将其放置其中。

insertion

算法思路¶

在做插入排序时，需要注意，在比较的时候就可以移动不符合顺序的数字，这样避免位置会错乱，而且可以保证效率。

在完成插入排序算法时，要注意以下几点：

在排序过程中，数组的前半部会形成有序区，后半部是未排序区。
在往前比较并且移动数字的过程中，注意终止条件。

算法的实现代码如下：

def insertion_sort(nums: List[int]):

    for i in range(0, len(nums)):
        temp = nums[i]
        for j in range(i, -1, -1):
            if j != 0 and temp < nums[j-1]:
                # 特别注意，当j = 0时，说明前面遍例所有的数都比当前数小，此时直接写入即可！
                # 当前位置的前一个数比temp小，说明此数还需要继续往后移动。
                nums[j] = nums[j-1]
            else:
                # 找到合适位置，即可插入
                nums[j] = temp
                break

算法性能¶

时间复杂度¶

同样的，请大家思考什么是最坏情况？最坏情况下的时间复杂度是什么？

空间复杂度¶

与上面两种算法相同，插入排序也只需要一下临时变量，所以空间复杂度也为 $O (1)$ 。

三种排序算法性能对比¶

在上面我们详细学习了三种的排序算法，下面列表中是这三种算法性能的对比。这三种算法思路比较简单，大家很快就能想到，但是可以看到其时间平均复杂度为 $O (n^{2})$ ，效率不是很理想。在实际情况中，除非在一些数据量比较小的场合，几乎很少采用三种算法。但是我同时可以看到，这三种算法的空间复杂度很低，基本上可以使用原数组的空间就能完成排序。

算法	最坏情况	平均情况	空间复杂度
冒泡排序	$O (n^{2})$	$O (n^{2})$	$O (1)$
选择排序	$O (n^{2})$	$O (n^{2})$	$O (1)$
插入排序	$O (n^{2})$	$O (n^{2})$	$O (1)$

第5课 排序算法（一）¶

冒泡排序算法（Bubble Sort）¶

算法思路¶

代码实现¶

性能分析¶

时间复杂度¶

空间复杂度¶

选择排序算法（Selection Sort）¶

算法思路¶

代码实现¶

算法性能分析¶

时间复杂度¶

空间复杂度¶

插入排序算法¶

算法思路¶

算法性能¶

时间复杂度¶

空间复杂度¶

三种排序算法性能对比¶

第5课排序算法（一）¶