【数据结构与算法笔记七】排序（上）

Posted on | Edited on | In

如何分析一个“算法”

排序算法的执行效率

1）最好情况、最坏情况、平均情况时间复杂度

在分析排序算法的时候，要分别给出最好情况、最坏情况、平均情况下的时间复杂度，以及对应情况下要排序的原始数据是什么样的（有序或者无序）。

2）时间复杂度的系数、常数、低阶

实际开发中，需要排序的数据可能是10个、100个、1000个这种小规模的数据，所以需要将时间复杂度的系数、常数、低阶都考虑到。

3）比较次数和交换/移动次数

基于比较的排序算法在执行过程中，会涉及到两种操作，一是元素比较大小，二是元素交换/移动。因此需要将比较次数和交换/移动次数也考虑进去。

排序算法的内存消耗

算法的内存消耗可以通过空间复杂度来衡量，排序算法也是。本文涉及到的三种排序算法都是空间复杂度为O(1)，也称为原地排序算法。原地排序算法是特指空间复杂度是O(1)的排序算法，也就是常量阶的时间复杂度。

排序算法的稳定性

排序算法的稳定性是指，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。如果排序之后，原本的前后顺序发生变化，那么对应的排序算法就叫做不稳定的排序算法。

应用：我们要给电商平台的订单数据进行排序，按照金额从小到大对订单数据进行排序。如果金额相同，那么就按照下单时间来排序。这时候就可以用到稳定的排序算法，先将订单都下单时间排序，排完序之后再对金额相同的订单从小到大排序。因为使用的是稳定的排序算法，所以第二次排序之后，相同金额的订单仍然保持下单时间从早到晚。

有序度、无序度、满有序度

一个长度为n的数组，有n！种排序方式，如果要计算排序算法的平均时间复杂度，涉及到的概率计算会非常复杂，所以使用“有序度”和“无序度”这两个概念来进行分析。这个方法并不严格，但是在很多时候很实用。

有序度是数组中具有有序关系的元素对的个数，用公式表示如下：

1
有序元素对：如果i < j，有a[i] <= a[j]

如数组[2, 4, 3, 1, 5, 6]的有序度为11，因为有序元素对有以下11个：

1
(2, 4), (2, 3), (4, 5), (4, 6), (2, 5), (2, 6), (3, 5), (3, 6), (1, 5), (1, 6), (5, 6)

对于一个倒序的数组来说，有序度就是0；如果是一个完全有序的数组，有序度是n(n-1)/2，也称为满有序度。那么，逆序度则与有序度的定义相反（默认从小到大为有序）。公式如下：

1
逆序元素对：如果i > j,有a[i] < a[j]

根据有序度和无序度的定义，可以得到这么一个公式：逆序度=满有序度-有序度。

对元素进行排序，就是一个不断增加有序度、减少逆序度的过程，直到达到满有序度，排序完成。

冒泡排序（Bubble Sort）

冒泡算法每次都只操作相邻的两个数据。如果不满足大小要求，就将其互换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 冒泡算法
def bubble_sort(a):
    """a是数组，返回从小到大排序的数组"""
    n = len(a)
    # 只有一个元素就直接返回
    if n <= 1:
        return a
    # 循环，将每个元素与下一个元素进行比较
    for i in range(n):
        flag = False
        for j in range(n-i-1):
            # 如果当前元素比下一个元素大，互换位置
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
                flag = True
        # 优化：没有数据交换，提前退出
        if not flag:
            break
    return a

a=[3,5,4,1,2,6,2,55,6,7,6,4]
bubble_sort(a)
分析冒泡算法

  1. 冒泡算法是原地排序算法吗

    因为只涉及到相邻数据的交换操作，需要的空间复杂度为O(1)，所以是原地排序算法。

  2. 冒泡算法是稳定的排序算法吗

    冒泡排序中只有交换才会改变两个元素的前后顺序。当相邻两个元素相等时，我们不做交换，所以大小相等的元素在排序前后顺序不改变，是稳定的排序算法。

  3. 冒泡排序的时间复杂度是多少

    最好情况下，要排序的数据已经是有序的了，只需要一次冒泡操作，所以最好情况时间复杂度为O(n)（遍历数组）。最坏情况则是，要排序的数据是倒序的，需要进行n次冒泡，所以最坏时间复杂度为O(n^2)。平均情况复杂度的计算，我们则可以根据有序度来计算。

    最坏情况下，初始状态的有序度是0，要进行n(n-1)/2次交换。最好情况情况下，初始状态的有序度是n(n-1)/2，不需要进行交换。我们可以取两者的中间值作为平均情况下的时间复杂度，也就是n(n-1)/4，所以复杂度为O(n^2)。

插入排序(Insertion Sort)

插入排序是在有序数组中插入新数据之后，仍然保持数据的有序性。所以需要遍历数组，找到数据应该插入的位置将其插入即可。

插入排序也只涉及到两种操作，一种是元素比较，另一种是元素的移动。

过程：我们需要将待排序数组分为已排序区和未排序区，一开始，已排序区只有一个元素，也就是数组的第一个元素。之后就不断在未排序区中取出元素，然后在已排序区遍历查找合适的位置插入新元素，同时将插入点之后的元素都顺序往后移动一位，并保证已排序区的数据一直有序。重复整个过程，直到未排序区的元素为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 插入排序
def insert_sort(a):
    n = len(a)
    if n <= 1:
        return 
    for i in range(1, n):
        # 当前元素
        value = a[i]
        for j in range(i, 0, -1):
            if a[j-1] > value:
                a[j-1], a[j] = value, a[j-1]
            else:
                break
    return a

b = [3,2,1,6,5,9,6,1]
insert_sort(b)
分析插入算法

  1. 插入排序是原地排序算法吗

    插入排序并不需要额外的储存空间，所以空间复杂度是O(1)，是原地排序算法。

  2. 插入排序是稳定的排序算法吗

    对于值相同的元素，我们可以将后面出现的元素插入到前面出现元素的后面，这样就保持了原本的前后顺序，从代码实现中也可以看出来。所以是稳定的排序算法。

  3. 插入排序的时间复杂度是多少

    最好情况下，待排序数组已经是有序的了，插入排序算法只是循环比较了一遍，并没有插入操作，所以最好情况时间复杂度为O(n)（遍历数组）。最坏情况下，待排序数组是倒序的，那么循环比较时，还需要移动数据，所以最坏情况时间复杂度为O(n^2)。插入排序类似于在数组中插入一个数据，只不过要循环执行n次插入操作，类比后者的平均时间复杂度是O(n)，插入排序算法的平均时间复杂度为O(n^2)。

选择排序(Selection Sort)

选择排序思路跟插入排序类似，也分未排序区和已排序区。不同的是，选择排序每次都从未排序区选择最小值插入到已排序区的尾部，也就是将两者互换。（打破了原有数组元素的前后顺序）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 选择排序
def select_sort(a):
    n = len(a)
    if n == 1:
        return a
    for i in range(n):
        # 最小元素的下标
        flag = i
        # 在未排序区选择最小元素
        for j in range(i, n):
            # 不断更新最小值
            if a[j] < a[flag]:
                # 如果元素小于最小元素，更新下标
                flag = j
        # 将最小元素与下标为i互换
        a[flag], a[i] = a[i], a[flag]
    return a

select_sort(a)
分析选择排序算法

  1. 选择排序是原地排序算法吗

    选择排序的空间复杂度为O(1)，所以是原地排序算法。

  2. 选择排序是稳定的排序算法吗

    每次选择元素都是在未排序区选择最小值然后与已排序区的末尾(未排序的第一位元素)元素进行交换，会打破原有元素的前后顺序。

  3. 选择排序的时间复杂度是多少

    不管待排序数组是有序还是倒序，每次选择最小元素的时候都会循环比较，执行n次这样的操作，所以不管最好情况时间复杂度、最坏情况时间复杂度和平均时间复杂度都是O(n^2)。

为什么插入排序要比冒泡排序更受欢迎

从上文可以得知，这两个算法的时间复杂度都是O(n^2)，都是原地排序算法，唯一的区别就在于数据交换部分。冒泡排序交换操作有三个操作语句，而插入排序的元素移动操作只有一行代码，所以从理论上来说，插入排序更优。

参考文章

数据结构与算法之美