🧭排序算法

排序算法的核心作用是 将一组数据按特定顺序排列，通常是按升序或降序排序。排序算法广泛应用于 数据处理、搜索优化和系统性能 中，是许多复杂任务的基础。

应用场景：

• 数据检索：通过排序优化搜索过程。例如，二分查找依赖于已排序的数据。
• 任务调度：排序可以帮助系统根据优先级调度任务（如操作系统的进程调度）。
• 数据压缩：一些压缩算法（如哈夫曼编码）需要先对数据进行排序以提高压缩效率。
• 推荐系统：按评分或相关性对内容进行排序，以向用户推荐最相关的结果。

简单来说，排序算法在提升数据处理效率、优化查询、改进存储和增强用户体验等方面都起着至关重要的作用。

一、冒泡排序

1. 基本思想

冒泡排序是一种通过相邻元素之间的比较和交换，逐步将“最大”元素“冒泡”到数组末端的排序算法。这个过程类似于水中的气泡上升，因此得名“冒泡排序”。

2. 工作原理

• 从数组的开始，依次比较相邻的元素，如果前一个元素大于后一个元素，则交换它们的位置。
• 每一次遍历，都会将当前未排序部分中的最大元素移动到数组的末端。
• 这个过程重复进行，直到所有元素都被排好序。

3. 冒泡排序的步骤

• 第一轮：从数组的第一个元素开始，依次和下一个元素比较，交换位置，直到最后一个元素。
• 第二轮：从第一个元素开始，重复比较和交换，直到倒数第二个元素。
• 第三轮：继续这个过程，直到剩下的元素只有一个时排序完成。

4. 程序

def bubble_sort(arr):
    n = len(arr)
    # 外层循环：控制比较的轮数 只需要 n - 2 次
    for i in range(n - 1): 
        swapped = False  # 用于检测这一轮是否有交换
        # 内层循环：进行相邻元素的比较
        for j in range(0, n-i-1):  # 这里的 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

5. 运行

arr = [64, 34, 25, 12, 22, 11, 90]
print("排序前:", arr)
sorted_arr = bubble_sort(arr)
print("排序后:", sorted_arr)

输出：

排序前: [64, 34, 25, 12, 22, 11, 90]
排序后: [11, 12, 22, 25, 34, 64, 90]

二、时间复杂度和空间复杂度

在算法复杂度分析中，O 是 “大O记号”（Big O notation）的简称，它是由德国数学家保罗・巴赫曼（Paul Bachmann）在 1892 年提出的一种数学符号，用于描述算法的时间复杂度或空间复杂度随输入规模增长的趋势。

时间复杂度和空间复杂度是算法分析中用来衡量算法效率的两个核心指标。

常见的时间复杂度：

• $O(1)$：常数时间复杂度，无论输入规模如何，执行时间固定。例如，访问数组中的某个元素。
• $O(logn)$：对数时间复杂度，常见于分治法或二分查找。例如，二分搜索每次将问题规模减半。
• $O(n)$：线性时间复杂度，执行时间与输入规模成正比。例如，遍历一个数组。
• $O(nlogn)$：线性对数时间复杂度，常见于高效排序算法，如快速排序或归并排序。
• $O(n²)$：平方时间复杂度，常见于嵌套循环。例如，冒泡排序或选择排序。
• $O(2ⁿ)$：指数时间复杂度，常见于递归解决组合问题，效率很低。
• $O(n!)$：阶乘时间复杂度，常见于旅行商问题等，规模稍大就几乎不可用。

1. 时间复杂度

时间复杂度描述的是算法执行时间随输入规模增长而变化的趋势，通常用大O记号（O(n)）表示。它反映了算法在最坏、平均或最佳情况下所需的计算步骤数量。

分析时间复杂度

1. 确定基本操作：找出算法中重复执行的核心操作（如比较、赋值）。
2. 统计操作次数：根据输入规模n，计算基本操作的执行次数。
3. 忽略常数和低阶项：用大O记号表示最高阶的增长趋势。例如，3n² + 2n + 5 ≈ O(n²)。

示例：

def sum_array(arr):
    total = 0           # O(1)
    for i in arr:       # O(n)，循环n次
        total += i      # O(1)
    return total        # O(1)

总时间复杂度：O(n)。

2. 空间复杂度 (Space Complexity)

空间复杂度描述的是算法在运行过程中占用的内存空间随输入规模增长的趋势，同样用大O记号表示。它包括：

• 固定空间：如临时变量、常量等，与输入规模无关。
• 可变空间：如递归调用栈、动态分配的数组等，与输入规模相关。

常见的空间复杂度：

• O(1)：常数空间复杂度，只使用固定数量的变量。例如，交换两个变量。
• O(n)：线性空间复杂度，分配与输入规模成正比的空间。例如，创建一个与输入数组等大的新数组。
• O(n²)：平方空间复杂度，常见于二维数组操作。
• O(log n)：对数空间复杂度，常见于递归算法的调用栈，如二分查找。

分析空间复杂度

1. 统计辅助空间：包括临时数组、递归调用栈等。
2. 考虑输入空间：通常不计入输入数据本身占用的空间，除非题目特别要求。
3. 取最高阶：与时间复杂度类似，忽略常数项和低阶项。

示例

def create_array(n):
    result = [0] * n    # O(n)，分配大小为n的数组
    for i in range(n):  # O(1)，循环只用常数空间
        result[i] = i
    return result

空间复杂度：O(n)。

3. 时间与空间的权衡

• 时间换空间：通过增加计算量减少内存使用。例如，牺牲一些重复计算来避免存储中间结果。
• 空间换时间：通过预存数据（如哈希表）加速计算。例如，动态规划中用表格存储子问题结果。

三、冒泡排序法的时间复杂度和空间复杂度

• 时间复杂度：

  • 最坏情况：O(n²)（逆序数组）。
  • 平均情况：O(n²)（随机排列）。
  • 最佳情况：O(n)（已排序数组，需优化版本）。

• 空间复杂度：O(1)（原地排序，仅用常数额外空间）。

时间复杂度分析

我们按照以下步骤分析时间复杂度：

1. 确定基本操作

冒泡排序的核心操作是：

• 比较：arr[j] > arr[j+1]。
• 交换：arr[j], arr[j+1] = arr[j+1], arr[j]。

2. 统计操作次数

• 外层循环：i 从 0 到 n-1，共运行 n 次。

• 内层循环：对于每个 i，j 从 0 到 n-i-1。因此：

  • 当 i=0，内层循环运行 n-1 次。

  • 当 i=1，内层循环运行 n-2 次。

  • ...

  • 当 i=n-1，内层循环运行 0 次。

  • 总比较次数（也是交换的最大可能次数）：

    $$(n-1)+(n-2)+\cdots +1=\frac{n(n-1)}{2}$$

    这是一个等差数列求和，约等于

    $$\frac{n^2}{2}-\frac{n}{2}$$

3. 忽略常数和低阶项

• 总操作次数近似为 $$\frac{n^2}{2} - \frac{n}{2}$$，最高阶为 $$n^2$$。
• 用大O记号表示，忽略常数和低阶项，时间复杂度为 O(n²)。

4. 不同情况下的时间复杂度

• 最坏情况（Worst Case）：数组完全逆序，每次内层循环都需要交换。时间复杂度为 O(n²)。
• 平均情况（Average Case）：随机排列，期望交换次数约为比较次数的一半，仍为 O(n²)。
• 最佳情况（Best Case）：数组已排序，无需交换。如果加一个标志位（flag）检查是否发生交换，可优化到 O(n)（只需一次外层循环）。

空间复杂度分析

我们按照以下步骤分析空间复杂度：

1. 统计辅助空间

• 固定空间：
  • 变量 n、i、j：占用常数空间，O(1)。
  • 在优化版本中，swapped 标志位：也是常数空间，O(1)。
• 可变空间：
  • 冒泡排序是原地排序算法，直接在输入数组上操作，没有分配额外的数组。
  • 没有递归调用，因此没有调用栈的额外空间。

2. 考虑输入空间

• 输入数组 arr 通常不计入空间复杂度（除非题目特别要求）。
• 即使计入，空间复杂度仍以辅助空间为主。

3. 取最高阶

• 辅助空间只有常数级变量（如 i, j, swapped），因此空间复杂度为 O(1)。

四、经典排序算法

1. 冒泡排序（Bubble Sort）

描述： 冒泡排序是一种简单的排序算法，通过多次比较相邻的元素，如果它们的顺序错误就交换它们的位置。每一次遍历都会将未排序部分的最大元素“冒泡”到最后。

特点：

• 简单，易于理解。
• 由于总是遍历所有元素，因此非常低效，特别是在数据量大的时候。

时间复杂度：

• 最好情况：$O(n)$（当数组已经排好序时）
• 平均情况：$O(n²)$
• 最坏情况：$O(n²)$

空间复杂度：$O(1)$

程序：

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

---

2. 选择排序（Selection Sort）

描述： 选择排序是一种简单的排序算法，每一轮从未排序部分选择最小元素并与未排序部分的第一个元素交换位置，逐渐将最小元素放到已排序部分的末尾。

特点：

• 每一轮都会选择最小元素，且不需要多次交换。
• 由于每次都需要扫描未排序部分，效率较低。

时间复杂度：

• 最好情况：$O(n²)$
• 平均情况：$O(n²)$
• 最坏情况：$O(n²)$

空间复杂度：$O(1)$

程序：

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

---

3. 插入排序（Insertion Sort）

描述： 插入排序通过构建一个有序序列，将未排序部分的元素逐个插入到已排序部分中，从而得到最终排序好的数组。

特点：

• 最好情况下时间复杂度为 O(n)（如果数据本身已近乎有序）。
• 对于大数据集效率较低。

时间复杂度：

• 最好情况：$O(n)$（数组已排序）
• 平均情况：$O(n²)$
• 最坏情况：$O(n²)$

空间复杂度：$O(1)$

程序：

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        # 将大于 key 的元素移动到下一个位置
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        # 插入 key 到正确的位置
        arr[j + 1] = key
    return arr

---

4. 希尔排序（Shell Sort）

Link → 希尔排序(算法过程, 效率, 稳定性分析)

描述： 希尔排序是插入排序的改进版本，由 Donald Shell 于 1959 年提出。它通过设置一系列的“增量 gap”，将原数组分成若干个“gap 间隔的子序列”，分别对每个子序列进行插入排序。当 gap 减小到 1 时，整个数组已经接近有序，再进行一次插入排序即可完成排序。原始的增量序列为 n//2, n//4, ..., 1。

特点：

• 相比于普通的插入排序，希尔排序减少了元素的移动次数。
• 使用增量序列对数组进行分组，可以大大提高效率。

时间复杂度：

• 最好情况：$O(nlogn)$
• 平均情况：和 Gap 取值有关，平均时间复杂度通常介于 $O(nlogn) $和 $O(n²)$
• 最坏情况：$O(n²)$

空间复杂度：$O(1)$

程序：

def shell_sort(arr):
    n = len(arr)
    gap = n // 2  # 初始间隔
    while gap > 0:
        # 对每个子序列进行插入排序
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2  # 缩小间隔
    return arr

---

5. 归并排序（Merge Sort）

Link → 归并排序(非递归与递归算法过程, 效率分析, 稳定性分析)

描述： 归并排序采用分治法，将数组分成两半，递归地对两半数组进行排序，然后将排序好的两半数组合并成一个有序数组。

特点：

• 时间复杂度为 $$O(n log n)$$，适用于大数据集。
• 需要额外的空间来存储临时数组。

时间复杂度：

• 最好情况：$O(nlogn)$
• 平均情况：$O(nlogn)$
• 最坏情况：$O(nlogn)$

空间复杂度：$O(n)$

程序：

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # 找到中点
        left_half = arr[:mid]
        right_half = arr[mid:]

        # 递归排序左右两部分
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        # 合并两个已排序部分
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # 处理剩余元素
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

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

---

6. 快速排序（Quick Sort）

描述： 快速排序也是采用分治法，将数组分为两部分，左部分所有元素小于右部分所有元素，然后递归地对这两部分继续进行排序。

特点：

• 在平均情况下，快速排序是最快的排序算法。
• 最坏情况下的时间复杂度为 $O(n²)$，但通过优化（如随机选择基准值）可以降低这种情况的发生。

时间复杂度：

• 最好情况：$O(nlogn)$
• 平均情况：$O(nlogn)$
• 最坏情况：$O(n²)$

空间复杂度：$O(logn)$（递归栈空间）

程序：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    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)

---

7. 计数排序（Counting Sort）

描述： 计数排序是一种非比较排序，它通过统计数组中每个元素的出现次数，然后根据计数信息来重新构建排序后的数组。

特点：

• 适用于数据范围较小的情况，且数据为整数。
• 时间复杂度为 $O(n+k)$，其中 $n$ 是数据元素个数，$k$ 是数据范围。

时间复杂度：

• 最好情况：$O(n+k)$
• 平均情况：$O(n+k)$
• 最坏情况：$O(n+k)$

空间复杂度：$O(k)$

程序：

def counting_sort(arr):
    max_val = max(arr)
    min_val = min(arr)
    range_of_elements = max_val - min_val + 1

    # 创建计数数组
    count = [0] * range_of_elements
    output = [0] * len(arr)

    # 存储每个元素出现的次数
    for num in arr:
        count[num - min_val] += 1

    # 累加计数数组，得到每个元素的最终位置
    for i in range(1, len(count)):
        count[i] += count[i - 1]

    # 生成排序后的数组
    for num in reversed(arr):
        output[count[num - min_val] - 1] = num
        count[num - min_val] -= 1

    return output

五、Python 的 Sort() 算法

在 Python 中，sort() 方法（用于列表排序）和 sorted() 函数（用于排序可迭代对象）采用的是一种名为 Timsort 的排序算法。这种算法是 Python 特有的高效排序实现，结合了归并排序和插入排序的优点。Timsort 是一种混合排序算法，由 Tim Peters 于 2002 年为 Python 语言设计，目前已成为 Python、Java（Android 平台）、Swift 等多种语言的标准排序算法实现。它的核心思想是结合了归并排序和插入排序的优势，并针对实际应用中常见的 “部分有序数据” 进行了优化。

为了提高算法的工作效率，sort()底层代码使用C语言来编写。

1. 核心设计思路

1. 适应现实数据特性 真实世界中的数据往往不是完全随机的，而是包含许多自然有序的片段（例如日志时间戳、已排序列表的拼接等）。Timsort 会先扫描数据，识别这些已有的有序片段（称为 “run”），并利用这些片段减少排序工作量。
2. 混合排序策略
   • 对小规模片段（默认阈值为 64 个元素）使用插入排序：插入排序在数据量小或基本有序时效率很高（常数项开销小）。
   • 对大规模数据使用归并排序：将多个有序 “run” 合并为更大的有序片段，最终得到完整的有序序列。
3. 稳定性保障 Timsort 是稳定排序算法，即相等元素的相对顺序在排序后保持不变（这对多字段排序等场景很重要）。

2. 基本步骤

1. 识别 “run”：遍历数据，划分出自然有序的片段（升序或降序，降序会被转为升序）。
2. 调整片段大小：若某个 “run” 长度小于阈值（通常为 64），用插入排序将其扩展到阈值长度。
3. 合并片段：用归并排序的思想合并所有 “run”，过程中会维护一个栈来平衡片段大小，确保合并效率。

3. 性能特点

• 时间复杂度：平均和最坏情况均为 O(n log n)，与归并排序相当。
• 实际表现：在真实数据（尤其是包含部分有序结构的数据）上，性能通常优于纯归并排序或快速排序。
• 空间复杂度：O(n)（归并过程需要临时空间存储中间结果）。

4. 应用场景

由于其对实际数据的适应性和稳定性，Timsort 特别适合：

• 处理可能包含部分有序的数据（如数据库查询结果、日志文件等）。
• 需要保持相等元素相对顺序的场景（如多关键字排序）。

这种算法设计体现了 “实用主义” 思想 —— 不局限于单一排序算法，而是根据数据特点动态调整策略，在真实场景中实现高效排序。