算法学习之基础排序

本文是学习排序系列的第一篇，主要介绍一些基本概念，对常见排序算法进行总结，以及介绍三种初级排序算法：冒泡、选择、插入

注：本文的排序算法默认升序

0. 写在前面

关于排序

排序算法是算法中较为基础的知识，给定一个无需序列，如何使其有序？这个问题目前拥有很多种解决方案，并且不同的方法也会涉及到不同的算法知识，比如常见的比较与非比较策略、迭代与递归的实现、分治策略、对算法的时间复杂度分析等

大O表示法

排序算法的稳定性

衡量一个排序算法的性能，我们不仅可以使用上述的大O表示法来表示算法的时间和空间复杂度，还可以判断其是否稳定。

如果Ai= Aj，排序前Ai在Aj之前，排序后Ai还在Aj之前，则称这种排序算法是稳定的。通俗地讲就是保证排序前后两个相等的数的相对顺序不变

• 对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。
• 排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。例如，对于冒泡排序，原本是稳定的排序算法，如果将记录交换的条件改成A[i] >= A[i + 1]，则两个相等的记录就会交换位置，从而变成不稳定的排序算法。
• 排序算法稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，前一个键排序的结果可以为后一个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位排序后元素的顺序在高位也相同时是不会改变的

1. 常见排序算法概览

1.1 按照排序方式分类

1. 一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)

   基于比较的排序算法，都免不了两种操作：比较与交换，所以在排序的过程中，我们可以通过计算比较操作与交换操作的次数来进一步衡量算法的有效性

   • 交换：冒泡排序、快速排序

   • 插入：简单插入排序、希尔排序

   • 选择：简单选择排序、堆排序

   • 归并：二路归并排序、多路归并排序

2. 另一种是非比较排序，时间复杂度可以达到O(n)

   • 计数排序

   • 桶排序

   • 基数排序

1.2 各排序算法对比

2. 常见排序算法学习

2.1 初级排序算法

先来看三种基于比较的排序算法，这三种算法较容易实现，但却不是最有效的，因为时间复杂度是平方级别。

冒泡排序(交换)(In-place)

冒泡排序是较为初级的排序算法，思想简单，易实现，但其算法复杂度不友好，一般仅做为入门学习。算法核心思想就是通过不断的比较以及交换，使极值元素向一端移动，类似冒泡的过程

给定一个N个元素的数组，冒泡排序将：

1. 比较一对相邻元素（a，b）
2. 如果元素大小关系不正确，交换这两个数（在本例中为a> b），
3. 重复步骤1和2，直到我们到达数组的末尾（最后一对是第（N-2）和（N-1）项，因为我们的数组从零开始）
4. 到目前为止，最大的元素将在最后的位置。 然后我们将N减少1，并重复步骤1，直到N = 1。

问题分析及优化

• 原始冒泡排序较为耗时，且其比较次数与序列无序程度无关，即使输入完全有序的序列，比较次数还是N * (N-1) / 2 次

• 针对上述问题，可以维护一个标志位，如果当前这一层的迭代过程中，没有发生元素位置的交换，那么说明前面所有元素都已经是有序的，就可以结束排序了

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def bubblesort(nums: List) -> List:
    length = len(nums)
    for i in range(1, length):
        sort_over = True
        for j in range(length-i):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
                sort_over = False
        if sort_over:
            return nums
    return nums

讨论

虽然优化后，冒泡排序在一般情况下运行得更快，但这种改进的想法并没有改变冒泡排序的 O(n^2) 时间复杂性…为什么？

优化的情况只是针对有序的条件，当序列完全逆序时，冒泡排序的比较次数和交换次数仍然非常多，不够有效

复杂度分析

针对优化后的冒泡排序，设定序列长度为N

• 时间复杂度

  最好情况下，序列完全有序，仅需比较 N-1 次，即可完成排序，无需交换，故时间复杂度为O(N)

  最坏情况下，序列完全逆序，需要比较(N-1) + (N-2) + ... + 1 + 0 = N*(N-1)/2，同理，需要交换N*(N-1)/2次，故时间复杂度为O(N^2)

• 空间复杂度

  因为是原地操作，所以空间复杂度为O(1)

是否稳定

冒泡排序是稳定的，因为其不改变相对顺序

选择排序(选择)(In-place)

选择排序也是基于比较的排序，其核心思想是比较(选择)、交换。相比与冒泡排序，选择排序大大减少了交换操作的次数，虽然时间复杂度与冒泡排序相同，但却更加高效

给定一个N个元素的数组，选择排序将从前向后遍历，假设当前元素为L，那么选择排序的方法是维护两部分内容，第一部分是L左侧的序列，该序列是升序有序的，第二部分是L以及L右侧的数据，可以理解为未排序的元素。所谓选择，就是每次都遍历从L到最后一个元素，选择最小的元素，并使其与L的位置交换。宏观上来看就是从L右边找到一个最小的，放到左边，然后不断右移L直到整个序列完全有序。具体可以分为三步

1. 在 [L … N-1]范围内找出最小项目X的位置

2. 用第 L 项交换X

3. 将下限 L 增加1并重复步骤1直到 L = N-2

看到这里，不难发现，相比于冒泡排序，选择排序的比较次数与冒泡排序一致，都是O(n^2)级别，但是实际交换的次数却只有O(n)次，这也是为什么选择排序会比冒泡排序快的原因。

代码

1
2
3
4
5
6
7
8
9

def selectsort(nums: List) -> List:
    length = len(nums)
    for i in range(length):
        min_id = i
        for j in range(i, length):
            min_id = j if nums[j] < nums[min_id] else min_id
        if min_id != i:    # 判断是否是当前元素最小，是的话就不用交换
            nums[min_id], nums[i] = nums[i], nums[min_id]
    return nums

复杂度分析

设定序列长度为N

• 时间复杂度

  最好情况下，序列完全有序，需比较 (N-1) + (N-2) + ... + 1 + 0 = N*(N-1)/2 次，即可完成排序，无需交换，故时间复杂度为O(N^2)

  最坏情况下，序列完全逆序，需要比较(N-1) + (N-2) + ... + 1 + 0 = N*(N-1)/2，同理，需要交换N-1次(无重复元素)，故时间复杂度为O(N^2)

• 空间复杂度

  因为是原地操作，所以空间复杂度为O(1)

是否稳定

选择排序是不稳定的，因为其在交换元素时可能改变相对顺序

插入排序(插入)(In-place)

插入排序类似‘打扑克’中我们抓牌码牌的过程，并且插入的思想使其平均操作次数小于选择排序，依据比较(交换)、插入的流程，插入排序的速度是三种基础排序算法中最快的

给定一个N个元素的数组，插入排序将从前向后遍历，假设当前元素为L，那么插入排序的方法是维护两部分内容，第一部分是L左侧的序列，该序列是升序有序的，第二部分是L以及L右侧的数据，可以理解为未排序的元素。所谓插入，就是在左侧有序序列中找到当前元素L的位置，使插入L后的序列依旧有序，然后依次右移L。可以总结为两步：

1. 将L依次与L左侧第n个元素比较(n=1,2,…)，我们称被比较的元素叫Ln，如果L大于Ln，交换二者位置，并继续向前比较，直到L小于或等于Ln，设定当前Ln的位置后一位为L，这时插入完毕

2. 更新L，重复1，直到遍历结束

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def insertsort(nums: List) -> List:
    length = len(nums)
    for i in range(length):
        cur_val = nums[i]
        last_id = i - 1

        while last_id >= 0 and nums[last_id] > cur_val:
            nums[last_id + 1] = nums[last_id]
            last_id -= 1

        nums[last_id + 1] = cur_val
    return nums

复杂度分析

设定序列长度为N

• 时间复杂度

  最好情况下，序列完全有序，外循环需N-1次，内循环主需要比较1次就会发现不需要交换，即可完成排序，故时间复杂度为O(N)

  最坏情况下，序列完全逆序，外循环需N-1次，内循环需要比较和交换O(n)级别的次数，故时间复杂度为O(N^2)

• 空间复杂度

  因为是原地操作，所以空间复杂度为O(1)

分析

上述过程说明了，插入排序在输入基本有序的情况下，时间复杂度可以达到O(N)级别，这已经很快了，但是当序列基本逆序的情况下，插入排序较为耗时的步骤在于，不断地比较与交换的操作，我们假设当前元素为L，L前面有K个元素已经处于有序状态，那么序列完全逆序时，L需要与这K个元素逐一比较并交换，对应的时间复杂度就是O(2K)，约等于O(K)级别，这依旧是较为耗时的，改进的方案有两种：

1. 二分

   将插入步骤中的比较过程，改为二分法，二分查找的方案比线性查找的时间复杂度低，毕竟是O(logK)与O(K)级别的对比，规模越大越明显，通过二分查找得到当前元素L应该插入的位置后，再将这个位置后面的元素统一后移一位，将L插入即可

2. 预处理

   这个思想仅需记住一点，插入排序对基本有序的输入，时间是很快的。

   那么所谓的预处理，我们可以通过某种方式使输入先变得相对有序一些，再进行插入排序，这样就会大大降低处理的耗时啦，这个思想其实就对应着插入排序的升级版本—希尔排序，下篇文章会详细介绍～

是否稳定

插入排序是稳定的，因为其在比较插入的过程中，遇到相等的元素并不进行交换

可视化网页

https://visualgo.net/zh/sorting

总结

1. 衡量排序算法好坏的标准有两个：复杂度以及稳定性

2. 冒泡排序通过不断比较、交换来使序列中的极值元素向序列的一端移动，形如冒泡

3. 选择排序则是通过选择操作取代了冒泡排序中冗余的交换次数，但却牺牲了稳定性

4. 插入排序在小数量级且序列基本有序时，表现的最快，原因是其在基本有序情况下，时间复杂度最小可以是O(N)级别，且操作次数少于冒泡排序。

5. 注意，复杂度分析是针对数量级进行的，同等数量级下，插入排序的操作次数就比冒泡排序少很多

最后，贴出个人测试的三种排序方式的时间对比，可见插入排序还是厉害的呀