概述

排序算法很基础，也很重要。排序算法有很多种，最经典，最常用的有：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。

分析

如何分析一个排序算法？

对于排序算法执行效率的分析，可以从执行效率、内存消耗和稳定性几个方面衡量。

执行效率（时间复杂度）

  1. 最好情况、最坏情况、平均情况时间复杂度
  2. 时间复杂度的系数、常数 、低阶
  3. 比较次数和交换（或移动）次数

内存消耗（空间复杂度）

对排序算法的空间复杂度，注意概念，原地排序（Sorted in place）。原地排序算法，就是特指空间复杂度是 O(1) 的排序算法，即不需要另外的空间。

稳定性（元素顺序）

排序算法的稳定性，是指如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

经过某种排序算法排序之后，如果相等元素的排序保持不变的话，就把这种排序算法叫作稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。

比如，给定一组数据，[5,2,3,4,3]经过排序算法后为[2,3,3,4,5]，若数组中两个3的先后顺序保持不变，则为稳定的排序算法。

有序度和逆序度

默认从小到大为有序。

有序度是数组中具有有序关系的元素对的个数。

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

逆序度是数组中具有逆序关系的元素对的个数。

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

完全有序的数组的有序度叫作满有序度。

1
满有序度的计算：n*(n-1)/2，n为元素的个数

公式：逆序度 = 满有序度 - 有序度。排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度，就说明排序完成了。

基本操作

比较和移动

O(n^2^)的排序算法

冒泡排序

描述

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
'''冒泡算法'''
def bubble_sort(a: List[int]):
    length = len(a)
    if length <= 1:
        return
        
    for i in range(length):
        # 提前退出冒泡循环的标志位
        made_swap = False
        for j in range(length-i-1):
            # 交换
            if a[j] > a[j+1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                # 表示有数据交换
                made_swap = True
        if not made_swap:
            break

分析

内存消耗和稳定性

冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。

在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

时间复杂度

  • 最好时间复杂度：最好情况下，初始状态的有序度是 n*(n-1)/2，就不需要进行交换。时间复杂度为 O(1)。
  • 最坏时间复杂度：最坏情况下，初始状态的有序度是 0，所以要进行 n*(n-1)/2 次交换。时间复杂度为 O(n^2)。
  • 平均时间复杂度：可以取中间值 n*(n-1)/4，来表示初始有序度既不是很高也不是很低的平均情况。平均情况下，需要 n*(n-1)/4 次交换操作，比较操作肯定要比交换操作多，而复杂度的上限是 O(n^2)，所以平均情况下的时间复杂度就是 O(n^2)。

插入排序

描述

将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。

插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
'''插入排序'''
def insertion_sort(a: List[int]):
    length = len(a)
    if length <= 1:
        return

    for i in range(1, length):
        # 这是提取的元素
        value = a[i]
        # 从i-1到0遍历
        j = i - 1
        # 若比提取的元素大，则往右移动
        while j >= 0 and a[j] > value:
            a[j + 1] = a[j]
            j -= 1
        # 否则插入提取的元素
        a[j + 1] = value

分析

插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 O(1)，也就是说，这是一个原地排序算法。

在插入排序中，对于值相同的元素，可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以平均时间复杂度为 O(n^2)。

选择排序

描述

将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。

选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
''' 选择排序 '''
def selection_sort(a: List[int]):
    length = len(a)
    if length <= 1:
        return

    for i in range(length):
        # 最小值索引
        min_index = i
        # 最小值
        min_val = a[i]
        for j in range(i, length):
            # 更新最小值索引和最小值
            if a[j] < min_val:
                min_index = j
                min_val = a[j]
        # 交换
        a[i], a[min_index] = a[min_index], a[i]

分析

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

选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 O(n^2)。

选择排序是一种不稳定的排序算法。选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。正是因此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。

小结

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

对比冒泡排序和插入排序，可以发现，在 Java 实现上，把执行一个赋值语句的时间粗略地计为单位时间（unit_time），然后分别用冒泡排序和插入排序对同一个逆序度是 K 的数组进行排序。用冒泡排序，需要 K 次交换操作，每次需要 3 个赋值语句，所以交换操作总耗时就是 3*K 单位时间。而插入排序中数据移动操作只需要 K 个单位时间。

因此，虽然冒泡排序和插入排序在时间复杂度上是一样的，都是 O(n^2)，但是如果希望把性能优化做到极致，那应该首选插入排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
冒泡排序中数据的交换操作：
if (a[j] > a[j+1]) { // 交换
   int tmp = a[j];
   a[j] = a[j+1];
   a[j+1] = tmp;
   flag = true;
}

插入排序中数据的移动操作：
if (a[j] > value) {
  a[j+1] = a[j];  // 数据移动
} else {
  break;
}

冒泡、插入、选择排序算法对比：

算法 原地？ 稳定？ 最好 最坏 平均
冒泡排序 √ √ O(n) O(n^2^) O(n^2^)
插入排序 √ √ O(n) O(n^2^) O(n^2^)
选择排序 √ × O(n^2^) O(n^2^) O(n^2^)

O(nlogn) 的排序算法

归并排序

描述

归并排序（Merge Sort）的思路是，如果要排序一个数组，先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

归并排序的核心是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。

递归就是计算数据规模不同、但求解思路相同的若干子问题，且具有终止条件的编程技巧。因此，可以用递归来解决归并排序的问题。

1
2
3
4
5
递推公式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

终止条件：
p >= r 不用再继续分解

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def merge_sort(a: List[int]):
    _merge_sort_between(a, 0, len(a) - 1)


def _merge_sort_between(a: List[int], low: int, high: int):
    # The indices are inclusive for both low and high.
    if low < high:
        mid = low + (high - low) // 2
        _merge_sort_between(a, low, mid)
        _merge_sort_between(a, mid + 1, high)
        _merge(a, low, mid, high)


def _merge(a: List[int], low: int, mid: int, high: int):
    # a[low:mid], a[mid+1, high] are sorted.
    i, j = low, mid + 1
    tmp = []
    while i <= mid and j <= high:
        if a[i] <= a[j]:
            tmp.append(a[i])
            i += 1
        else:
            tmp.append(a[j])
            j += 1
    start = i if i <= mid else j
    end = mid if i <= mid else high
    tmp.extend(a[start:end + 1])
    a[low:high + 1] = tmp

分析

稳定性

归并排序可以保证值相同的元素，在合并前后的先后顺序不变。因此，归并排序是一个稳定的排序算法。

时间复杂度

假设对 n 个元素进行归并排序需要的时间是 T(n)，那分解成两个子数组排序的时间都是 T(n/2)，merge() 函数合并两个有序子数组的时间复杂度是 O(n)。

1
2
T(1) = C； n=1时，只需要常量级的执行时间，所以表示为C。
T(n) = 2*T(n/2) + n； n>1

进一步推导，可以得到 T(n) = 2^k^ * T(n/2^k^)+kn。

1
2
3
4
5
6
T(n) = 2*T(n/2) + n
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     ......
     = 2^k * T(n/2^k) + k * n
     ......

当 T(n/2^k^) = T(1)，即 n/2^k^ = 1 时，k = log2n。将 k 值代入上述公式，可得 T(n) = Cn + nlog2n。因此，归并排序的时间复杂度为 O(nlogn)。

空间复杂度

归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间。因此，归并排序不是一个原地排序算法。

尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。

快速排序

描述

快速排序算法（Quicksort），简称快排。

快排的核心思想是分治和分区。

思路：假设要排序数组中下标从 p 到 r 之间的一组数据。

  1. 选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。
  2. 遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。
  3. 此时，数组分为三段，p:q-1、q、q+1:r，分别小于、等于和大于 pivot。
  4. 用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间缩小为 1。此时，数组有序。
1
2
3
4
5
递推公式：
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1… r)

终止条件：
p >= r

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def quick_sort(a: List[int]):
    _quick_sort_between(a, 0, len(a) - 1)


def _quick_sort_between(a: List[int], low: int, high: int):
    if low < high:
        # get a random position as the pivot
        k = random.randint(low, high)
        a[low], a[k] = a[k], a[low]

        m = _partition(a, low, high)  # a[m] is in final position
        _quick_sort_between(a, low, m - 1)
        _quick_sort_between(a, m + 1, high)


def _partition(a: List[int], low: int, high: int):
    pivot, j = a[low], low
    for i in range(low + 1, high + 1):
        if a[i] <= pivot:
            j += 1
            a[j], a[i] = a[i], a[j]  # swap
    a[low], a[j] = a[j], a[low]
    return j

分析

稳定性

因为分区的过程涉及交换操作，如果数组中有两个相同的元素，在经过分区操作之后，元素的相对先后顺序可能会改变，因此，快排不是一个稳定的排序算法。

空间复杂度

快排的 partition 函数，利用了元素之间的交换，不需要占用额外的内存空间，所以快排的空间复杂度为 O(1)，因此，快排是原地排序算法。

时间复杂度

快排的时间复杂度与归并排序类似，是 O(nlogn)。但是，如果数组中的元素已经是有序的了，且每次都选择最后一个元素作为 pivot，那每次分区得到的两个区间都是极不均等的。需要进行大约 n 次分区操作，才能完成快排的整个过程。每次分区平均要扫描大约 n/2 个元素，这种情况下，快排的时间复杂度就从 O(nlogn) 退化成了 O(n2)。

小结

归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。

理解归并排序的重点是理解递推公式和 merge() 合并函数。同理，理解快排的重点也是理解递推公式，还有 partition() 分区函数。

归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法，但是归并排序不是原地排序算法，空间复杂度比较高，是 O(n)，因此，归并排序没有快排应用广泛。

快排虽然最坏的时间复杂度为O(n^2)，但其时间复杂度退化到 O(n^2) 的概率非常小，而且可以通过合理地选择 pivot 来避免这种情况。

归并、快速排序算法对比：

算法 原地？ 稳定？ 最好 最坏 平均
归并排序 × √ O(nlogn) O(nlogn) O(nlogn)
快速排序 √ × O(nlogn) O(n^2) O(nlogn)

O(n) 的排序算法