术之尽头：排序算法优化思考

信息

2024年8月6日 · ·

在上篇《计算机工程师之路》中我们谈到了工程师的打怪升级之路。在计算的世界，算法是我们内练的“一口气”，是开启工程师之路最基本的素养。本文从最常见的排序算法出发，探讨算法优化的思路：算法的优化过程其实就是一个消除无用功的过程。

引言

排序算法是人们研究的最多的一类计算机算法，也是计算机中最基础、使用频率最高的一类算法。虽然对排序算法的理论研究在目前看来被认为已经是最优解，但面对工业界各类问题，人们还是持续提出了针对特定场景的“更优”的算法。通过对排序算法的研究和优化，我们可以清晰的感受和思考算法优化的过程与诀窍。

未优化的排序算法

未优化的排序算法包括选择排序、冒泡排序、插入排序，它们的实现都很直观，并且在 n 较小时效果较好。然而，由于时间复杂度为 $O(n^2)$ ，它们在处理大数据集时表现不佳。

选择排序（Selection Sort）

选择排序的基本思路是重复找到剩余元素的最小值，并将其移到已排序部分的末尾。

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# 测试选择排序
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("选择排序结果:", sorted_arr)
# 选择排序结果: [11, 12, 22, 25, 64]

冒泡排序（Bubble Sort）

冒泡排序的基本思路是重复遍历数组，比较相邻元素，如果顺序错误就交换，最终将最大的元素移到末尾。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

# 测试冒泡排序
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("冒泡排序结果:", sorted_arr)
# 冒泡排序结果: [11, 12, 22, 25, 34, 64, 90]

插入排序（Insertion Sort）

插入排序的基本思路是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# 测试插入排序
arr = [12, 11, 13, 5, 6]
print("插入排序结果:", insertion_sort(arr))
# 插入排序结果: [5, 6, 11, 12, 13]

优化的排序算法

优化的排序算法一般指：归并排序、堆排序、快速排序。这些算法各有优缺点，在不同的数据和场景下表现不同。归并排序和堆排序适合较大数据集且保证稳定性，快速排序一般在大多数情况下表现较优异，但在最坏情况下的表现（如选取基准不当）时需要注意。

归并排序（Merge Sort）

归并排序的基本思想是分治法，将数组分成两部分分别排序，然后将排序好的两部分合并。

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
    return arr

# 测试归并排序
arr = [12, 11, 13, 5, 6, 7]
print("归并排序结果:", merge_sort(arr))
# 归并排序结果: [5, 6, 7, 11, 12, 13]

堆排序（Heap Sort）

堆排序的基本思想是先构建一个最大堆，然后不断将堆顶元素与最后一个元素交换，重建堆，直到排序完成。

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

    return arr

# 测试堆排序
arr = [12, 11, 13, 5, 6, 7]
print("堆排序结果:", heap_sort(arr))
# 堆排序结果: [5, 6, 7, 11, 12, 13]

快速排序（Quick Sort）

快速排序的基本思想是通过一个基准元素将待排序数组分成两部分，比基准小的在左边，比基准大的在右边，然后递归地对每部分进行快速排序。

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
        return quick_sort(left) + middle + quick_sort(right)

# 测试快速排序
arr = [3, 6, 8, 10, 1, 2, 1]
print("快速排序结果:", quick_sort(arr))
# 快速排序结果: [1, 1, 2, 3, 6, 8, 10]

混合排序

蒂姆排序（TimSort）

蒂姆排序是结合了插入排序和归并排序的一种混合算法。它首先将数组分割成若干较小的区块（称为“run”），对这些区块进行插入排序，然后利用归并排序将这些有序区块合并起来。蒂姆排序是 Python 语言中 sort() 方法和 Java 语言中 Arrays.sort() 方法的底层实现。

MIN_RUN = 32

def insertion_sort(arr, left, right):
    for i in range(left + 1, right + 1):
        key = arr[i]
        j = i - 1
        while j >= left and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

def merge(arr, left, mid, right):
    len1, len2 = mid - left + 1, right - mid
    left_part, right_part = [], []

    for i in range(0, len1):
        left_part.append(arr[left + i])
    for i in range(0, len2):
        right_part.append(arr[mid + 1 + i])

    i, j, k = 0, 0, left

    while i < len1 and j < len2:
        if left_part[i] <= right_part[j]:
            arr[k] = left_part[i]
            i += 1
        else:
            arr[k] = right_part[j]
            j += 1
        k += 1

    while i < len1:
        arr[k] = left_part[i]
        k += 1
        i += 1

    while j < len2:
        arr[k] = right_part[j]
        k += 1
        j += 1

def tim_sort(arr):
    n = len(arr)

    for start in range(0, n, MIN_RUN):
        end = min(start + MIN_RUN - 1, n - 1)
        insertion_sort(arr, start, end)

    size = MIN_RUN
    while size < n:
        for left in range(0, n, size * 2):
            mid = min(n - 1, left + size - 1)
            right = min((left + 2 * size - 1), (n - 1))
            if mid < right:
                merge(arr, left, mid, right)
        size *= 2

# 测试蒂姆排序
arr = [5, 21, 7, 23, 19, 10, 20, 12, 22, 14]
tim_sort(arr)
print("蒂姆排序结果:", arr)
# 蒂姆排序结果: [5, 7, 10, 12, 14, 19, 20, 21, 22, 23]

在上述实现中：

insertion_sort：对每个小区块（run）进行插入排序。
merge：将两个已经排序的区块合并成一个有序区块。
tim_sort：首先切分数组并对每个小区块进行插入排序，然后通过归并排序逐步合并这些有序区块。

这种结合插入排序和归并排序的方式，使蒂姆排序在处理大数据且包含部分已排序数据时有着优异的性能表现。

性能概览与分析

下面是这些排序算法的时间复杂度、空间复杂度、最差计算复杂度和平均计算复杂度列表：

排序算法	时间复杂度 (最坏)	时间复杂度 (平均)	空间复杂度	最差计算复杂度	稳定性
选择排序	$O(n^2)$	$O(n^2)$	O(1)	$O(n^2)$	不稳定
冒泡排序	$O(n^2)$	$O(n^2)$	O(1)	$O(n^2)$	稳定
插入排序	$O(n^2)$	$O(n^2)$	O(1)	$O(n^2)$	稳定
归并排序	$O(n\log{n})$	$O(n\log{n})$	O(n)	$O(n\log{n})$	稳定
堆排序	$O(n\log{n})$	$O(n\log{n})$	O(1)	$O(n\log{n})$	不稳定
快速排序	$O(n^2)$	$O(n\log{n})$	$O(\log{n})$	$O(n^2)$	不稳定
蒂姆排序	$O(n\log{n})$	$O(n\log{n})$	O(n)	$O(n\log{n})$	稳定

选择排序

时间复杂度: 在最坏和平均情况下，整个数组都需要两两比较，每次找出最小值放到已排序部分，因此是 $O(n^2)$ 。
空间复杂度: 只使用了常数级额外空间，故为 O(1)。
稳定性: 由于交换可能会打破相同元素之间的顺序，所以是不稳定的。

冒泡排序

时间复杂度: 在最坏和平均情况下，每次遍历都需要多次交换，比较次数是 $O(n^2)$ 。
空间复杂度: 只使用了常数级额外空间，故为 O(1)。
稳定性: 每次交换只针对相邻元素，故是稳定的。

插入排序

时间复杂度: 在最坏和平均情况下，新元素可能需要遍历到已排序部分的最左端，所以时间复杂度为 $O(n^2)$ 。
空间复杂度: 只使用了常数级额外空间，故为 O(1)。
稳定性: 插入排序不会改变相同元素的相对顺序，所以是稳定的。

归并排序

时间复杂度: 无论在最坏情况还是平均情况，归并排序都会递归地将数组一分为二并合并，时间复杂度是 $O(n\log{n})$ 。
空间复杂度: 需要额外的数组空间来存储合并后的结果，因此空间复杂度是 O(n)。
稳定性: 合并过程中不会改变相同元素的相对顺序，所以是稳定的。

堆排序

时间复杂度: 无论在最坏情况还是平均情况，堆排序都需要构建和调整堆，时间复杂度为 $O(n\log{n})$ 。
空间复杂度: 使用原地排序，只是用常数级额外空间，故为 O(1)。
稳定性: 由于堆调整过程中同值元素可能会被重排序，故是不稳定的。

快速排序

时间复杂度: 在最坏情况下（数组已排序或者逆序，且选择第一个元素为枢纽），需要 $O(n^2)$ 的比较次数；但是平均情况下，通过分而治之，时间复杂度为 $O(n\log{n})$ 。
空间复杂度: 递归调用会使用栈空间，但在平均情况下为 $O(\log{n})$ ，最坏情况下为 O(n)。
稳定性: 交换可能会改变相同元素的相对顺序，所以是不稳定的。

蒂姆排序

时间复杂度: 在最坏和平均情况下，通过合并已经排序的 run 加速整个排序过程，时间复杂度为 $O(n\log{n})$ 。
空间复杂度: 需要额外的数组空间来存储合并的结果，因此空间复杂度是 O(n)。
稳定性: 在合并过程中保持相同元素的相对顺序，所以是稳定的。

排序算法优化思路

从上述 7 中排序算法的基本思路和性能表现对比不难看出，算法的优化过程其实就是一个消除无用功的过程。在设计算法时，我们首先要弄清楚哪些计算是必要的，哪些计算是多余的，将多余的部分全部挑出来省掉。

其次，我们可以从 7 个排序算法中看到一些常见的解题思路，比如递归、分治等逆向的计算思维方式。

递归思想

递归是通过直接或间接调用函数自身来解决问题的一种方法。递归通常应用于分治策略，通过将问题分解成更小的同类问题来进行求解。这在降低计算复杂度方面特别有用。

递归算法通常包含两个部分：

基本情况(Base Case)：初始的、最简单的、可以直接得出结果的情况。
递归情况(Recursive Case)：将问题分解为更小的子问题，并调用自身求解这些子问题。

示例：降低 Fibonacci 数列的计算复杂度

def fibonacci(n):
    if n <= 1:  # 基本情况
        return n
    else:       # 递归情况
        return fibonacci(n-1) + fibonacci(n-2)

# 测试
print(fibonacci(10))
# Output: 55

递归思想在计算机科学中被广泛应用，通过将复杂问题分解为更小的部分并递归求解，合理设计数据结构和算法来最大化剔除中间冗余的计算，可以有效地降低时间复杂度。

递归有时非常简洁易懂，但每次递归调用都会消耗栈空间，存在风险。因此，在实际开发中，特别是对于大规模数据，可能会更倾向于使用迭代以避免栈溢出问题。

分治算法

分治算法（Divide and Conquer）是一种通过将问题递归地分解成若干个规模更小但类型相同的子问题，分别解决这些子问题，再将它们的结果合并来得到原问题的解的方法。这种方法经常用于需要将复杂问题化简的场景中，上文的归并排序和快速排序中就应用了分治算法。

分治算法的核心思想包括三个部分：

分解（Divide）：将原问题分解成若干个规模更小的子问题。
解决（Conquer）：递归地解决这些子问题。如果子问题足够小，可以直接得出结果。
合并（Combine）：将子问题的结果合并起来，得到原问题的解。

分治算法的一般形式可以表示为：

定义基本情况（Base Case）：即当问题规模足够小时，直接得出结果。
划分问题（Divide）：将问题划分为更小的子问题。
求解子问题（Conquer）：递归地求解子问题。
合并结果（Combine）：将子问题的解合并获得原问题的解。

上文的归并排序将数组分成两半，递归地进行排序，然后合并这两个有序的部分，最终使时间复杂度降为 $O(n\log{n})$ 。

对于大多数情况，分治策略能大大提高算法的效率，且分治算法思想清晰，通常简洁而富有逻辑性。但递归调用可能会使用较多的栈空间，特别是对于空间复杂度不太优化的实现。在某些情况下，比如快速排序选取了不合适的基准值，可能导致分割不平衡，这也会影响算法效率。

总之，分治算法是一种强大而通用的方法，能够有效地降低问题的复杂度，尤其是在处理大规模数据时。

逆向思维

计算机在处理任务时，往往是采取自顶向下、先全局后具备的逆向思维方式，这与人类习惯于从个例中总结归纳出一般性规律的思维方式正好相反。逆向思维是一种从问题的最终目标开始，逐步倒退推导出解决方案的算法设计方法。相比于自底向上的递推，逆向思维通常采用反向分析来找到简化和优化问题的路径。递归与分治就是逆向思维的典型代表。

示例：动态规划中的最短路径问题

问题：给定一个二维网格，每个格子有一个非负权值，找到从起点（左上角）到终点（右下角）的最小路径和。

逆向思维解决方案：

目标：我们要从终点回推到起点。
状态转移：设 dp[i][j] 表示到达格子 (i, j) 的最小路径和，那么：
- 如果从上方来：dp[i][j] = dp[i-1][j] + grid[i][j]
- 如果从左方来：dp[i][j] = dp[i][j-1] + grid[i][j]
- 综合以上两点，我们有：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
边界条件：起点 dp[0][0] = grid[0][0]。

完整代码如下：

def min_path_sum(grid):
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]

    dp[0][0] = grid[0][0]

    for i in range(1, rows):
        dp[i][0] = dp[i-1][0] + grid[i][0]

    for j in range(1, cols):
        dp[0][j] = dp[0][j-1] + grid[0][j]

    for i in range(1, rows):
        for j in range(1, cols):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

    return dp[rows-1][cols-1]

# 测试
grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]
print("最小路径和:", min_path_sum(grid))  # 输出: 7

逆向思维是一种强大的算法设计策略，通过从目标倒推问题，能够有效地简化问题结构，避免重复计算。在实际应用中，结合具体问题特性，逆向思维与动态规划、记忆化等方法往往能够高效地求解复杂问题。

结语

本文从基础的未优化排序算法到高效的优化排序算法，再到混合排序算法的精妙设计，深入探讨了排序算法的优化之道。通过对不同排序算法的分析和比较，我们不仅理解了它们的工作原理，学习了如何根据不同的应用场景选择或设计合适的排序算法，更是加深了我们对问题本质的理解，启发了我们的逻辑思维和创新能力。

始终记住，算法优化的核心其实就是识别并消除冗余的计算。合理利用数据结构和算法设计技巧，灵活运用递归、分治、动态规划等策略思想，以计算机的视角来处理问题。

希望本文能够激发读者对算法优化的兴趣与思路。让我们一起在计算的世界里，不断前行，探索未知，创造可能！

PS：感谢每一位志同道合者的阅读，欢迎关注、点赞、评论！

引言​

未优化的排序算法​

选择排序（Selection Sort）​

冒泡排序（Bubble Sort）​

插入排序（Insertion Sort）​

优化的排序算法​

归并排序（Merge Sort）​

堆排序（Heap Sort）​

快速排序（Quick Sort）​

混合排序​

蒂姆排序（TimSort）​

性能概览与分析​

选择排序​

冒泡排序​

插入排序​

归并排序​

堆排序​

快速排序​

蒂姆排序​

排序算法优化思路​

递归思想​

分治算法​

逆向思维​

结语​

引言